INTERNATIONAL GONGRESS {:[" OF MATHEMATIGIANS "],[2022" JULY "6-14]:}\begin{aligned} & \text { OF MATHEMATIGIANS } \\ & 2022 \text { JULY } 6-14\end{aligned}
ISBN 978-3-98547-058-7, eISBN 978-3-98547-558-2, DOI 10.4171/ICM2O22
Volume 1. Prize Lectures
ISBN 978-3-98547-059-4, eISBN 978-3-98547-559-9, DOI 10.4171/ICM2022-1
Volume 2. Plenary Lectures
ISBN 978-3-98547-060-0, eISBN 978-3-98547-560-5, DOI 10.4171/ICM2022-2
rarr\rightarrow Volume 3. Sections 1-4
ISBN 978-3-98547-061-7, eISBN 978-3-98547-561-2, DOI 10.4171/ICM2022-3
Volume 4. Sections 5-8
ISBN 978-3-98547-062-4, eISBN 978-3-98547-562-9, DOI 10.4171/ICM2022-4
Volume 5. Sections 9-11
ISBN 978-3-98547-063-1, eISBN 978-3-98547-563-6, DOI 10.4171/ICM2022-5
Volume 6. Sections 12-14
ISBN 978-3-98547-064-8, eISBN 978-3-98547-564-3, DOI 10.4171/ICM2022-6
Volume 7. Sections 15-20
ISBN 978-3-98547-065-5, eISBN 978-3-98547-565-0, DOI 10.4171/ICM2022-7
The content of this volume is licensed under the CC BY 4.0 license, with the exception of the logos and branding of the International Mathematical Union and EMS Press, and where otherwise noted.
Bibliographic information published by the Deutsche Nationalbibliothek
The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie;
detailed bibliographic data are available on the Internet at http://dnb.dnb.de.
Published by EMS Press, an imprint of the
European Mathematical Society - EMS - Publishing House GmbH
Typesetting using the authors' LaTeX sources: VTeX, Vilnius, Lithuania
Printed in Germany
@ Printed on acid free paper
CONTENTS
VOLUME 1
Foreword ..... V
International Congresses of Mathematicians ..... 1
Fields medalists and IMU prize winners ..... 3
Opening greetings by the IMU President ..... 5
Closing remarks by the IMU President ..... 9
Status report for the IMU ..... 11
Photographs ..... 21
THE WORK OF THE FIELDS MEDALISTS AND THE IMU PRIZE WINNERS
Martin Hairer, The work of Hugo Duminil-Copin ..... 26
Gil Kalai, The work of June Huh ..... 50
Kannan Soundararajan, The work of James Maynard ..... 66
Henry Cohn, The work of Maryna Viazovska ..... 82
Ran Raz, The work of Mark Braverman ..... 106
Henri Darmon, The work of Barry Mazur ..... 118
Rupert L. Frank, The work of Elliott Lieb ..... 142
Tadashi Tokieda, Nikolai Andreev and the art of mathematical animation and model-
building ..... 160
Kevin Buzzard, What is the point of computers? A question for pure mathematicians ..... 578
Frank Calegari, Reciprocity in the Langlands program since Fermat's Last Theorem ..... 610
Frans Pretorius, A survey of gravitational waves ..... 652
PLENARY LECTURES
Mladen Bestvina, Groups acting on hyperbolic spaces-a survey ..... 678
Bhargav Bhatt, Algebraic geometry in mixed characteristic ..... 712
Thierry Bodineau, Isabelle Gallagher, Laure Saint-Raymond, Sergio Simonella,
Dynamics of dilute gases: a statistical approach ..... 750
Alexander Braverman, David Kazhdan, Automorphic functions on moduli spaces of
bundles on curves over local fields: a survey ..... 796
Tobias Holck Colding, Evolution of form and shape ..... 826
Camillo De Lellis, The regularity theory for the area functional (in geometric mea-
sure theory) ..... 872
Weinan E, A mathematical perspective of machine learning ..... 914
Craig Gentry, Homomorphic encryption: a mathematical survey ..... 956
Alice Guionnet, Rare events in random matrix theory ..... 1008
Larry Guth, Decoupling estimates in Fourier analysis ..... 1054
Svetlana Jitomirskaya, One-dimensional quasiperiodic operators: global theory, dual-
ity, and sharp analysis of small denominators ..... 1090
Igor Krichever, Abelian pole systems and Riemann-Schottky-type problems . . ..... 1122
Alexander Kuznetsov, Semiorthogonal decompositions in families ..... 1154
Scott Sheffield, What is a random surface? ..... 1202
Kannan Soundararajan, The distribution of values of zeta and L-functions ..... 1260
Catharina Stroppel, Categorification: tangle invariants and TQFTs ..... 1312
Michel Van den Bergh, Noncommutative crepant resolutions, an overview ..... 1354
Avi Wigderson, Interactions of computational complexity theory and mathematics ..... 1392
List of contributors ..... 1433
VOLUME 3
1. LOGIC
Gal Binyamini, Dmitry Novikov, Tameness in geometry and arithmetic: beyond
o-minimality ..... 1440
Natasha Dobrinen, Ramsey theory of homogeneous structures: current trends and
open problems ..... 1462
Andrew S. Marks, Measurable graph combinatorics ..... 1488
Keita Yokoyama, The Paris-Harrington principle and second-order arithmetic-
bridging the finite and infinite Ramsey theorem ..... 1504
2. ALGEBRA
Pierre-Emmanuel Caprace, George A. Willis, A totally disconnected invitation to locally compact groups 1554
Neena Gupta, The Zariski cancellation problem and related problems in affine algebraic geometry
Syu Kato, The formal model of semi-infinite flag manifolds ..................... 1600
Michael J. Larsen, Character estimates for finite simple groups and applications . . 1624
Amnon Neeman, Finite approximations as a tool for studying triangulated categories 1636
Irena Peeva, Syzygies over a polynomial ring ....................................... 1660
3. NUMBER THEORY - SPECIAL LECTURE
Joseph H. Silverman, Survey lecture on arithmetic dynamics
1682
3. NUMBER THEORY
Ana Caraiani, The cohomology of Shimura varieties with torsion coefficients . . . 1744
Samit Dasgupta, Mahesh Kakde, On the Brumer-Stark conjecture and refinements 1768
Alexander Gamburd, Arithmetic and dynamics on varieties of Markoff type ...... 1800
Philipp Habegger, The number of rational points on a curve of genus at least two . 1838
Atsushi Ichino, Theta lifting and Langlands functoriality ........................ 1870
Dimitris Koukoulopoulos, Rational approximations of irrational numbers ........ 1894
David Loeffler, Sarah Livia Zerbes, Euler systems and the Bloch-Kato conjecture for
automorphic Galois representations . ................................................................. 1918
Lillian B. Pierce, Counting problems: class groups, primes, and number fields . . . 1940
Ye Tian, The congruent number problem and elliptic curves .......................... 1990
Xinwen Zhu, Arithmetic and geometric Langlands program ....................... 2012
4. ALGEBRAIC AND COMPLEX GEOMETRY - SPECIAL LECTURE
Marc Levine, Motivic cohomology .................................................... 2048
4. ALGEBRAIC AND COMPLEX GEOMETRY
Mina Aganagic, Homological knot invariants from mirror symmetry ..... 2108
Aravind Asok, Jean Fasel, Vector bundles on algebraic varieties ..... 2146
Arend Bayer, Emanuele Macrì, The unreasonable effectiveness of wall-crossing in
algebraic geometry ..... 2172
Vincent Delecroix, Élise Goujard, Peter Zograf, Anton Zorich, Counting lattice
points in moduli spaces of quadratic differentials ..... 2196
Alexander I. Efimov, K-theory of large categories ..... 2212
Tamás Hausel, Enhanced mirror symmetry for Langlands dual Hitchin systems ..... 2228
Bruno Klingler, Hodge theory, between algebraicity and transcendence ..... 2250
Chi Li, Canonical Kähler metrics and stability of algebraic varieties ..... 2286
Aaron Pixton, The double ramification cycle formula ..... 2312
Yuri Prokhorov, Effective results in the three-dimensional minimal model program ..... 2324
Olivier Wittenberg, Some aspects of rational points and rational curves ..... 2346
List of contributors ..... 2369
VOLUME 4
5. GEOMETRY - SPECIAL LECTURES
Bruce Kleiner, Developments in 3D Ricci flow since Perelman ..... 2376
Richard Evan Schwartz, Survey lecture on billiards ..... 2392
5. GEOMETRY
Richard H. Bamler, Some recent developments in Ricci flow ..... 2432
Robert J. Berman, Emergent complex geometry ..... 2456
Danny Calegari, Sausages ..... 2484
Kai Cieliebak, Lagrange multiplier functionals and their applications in symplectic
geometry and string topology ..... 2504
Penka Georgieva, Real Gromov-Witten theory ..... 2530
Hiroshi Iritani, Gamma classes and quantum cohomology ..... 2552
Gang Liu, Kähler manifolds with curvature bounded below ..... 2576
Kathryn Mann, Groups acting at infinity ..... 2594
Mark McLean, Floer cohomology, singularities, and birational geometry ..... 2616
Iskander A. Taimanov, Surfaces via spinors and soliton equations ..... 2638
Lu Wang, Entropy in mean curvature flow ..... 2656
Robert J. Young, Composing and decomposing surfaces and functions ..... 2678
Xin Zhou, Mean curvature and variational theory ..... 2696
Xiaohua Zhu, Kähler-Ricci flow on Fano manifolds ..... 2718
6. TOPOLOGY
Jennifer Hom, Homology cobordism, knot concordance, and Heegaard Floer homol-
ogy ..... 2740
Daniel C. Isaksen, Guozhen Wang, Zhouli Xu, Stable homotopy groups of spheres
and motivic homotopy theory ..... 2768
Yi Liu, Surface automorphisms and finite covers ..... 2792
Roman Mikhailov, Homotopy patterns in group theory ..... 2806
Thomas Nikolaus, Frobenius homomorphisms in higher algebra ..... 2826
Oscar Randal-Williams, Diffeomorphisms of discs ..... 2856
Jacob Rasmussen, Floer homology of 3-manifolds with torus boundary ..... 2880
Nathalie Wahl, Homological stability: a tool for computations ..... 2904
7. LIE THEORY AND GENERALIZATIONS
Evgeny Feigin, PBW degenerations, quiver Grassmannians, and toric varieties ..... 2930
Tasho Kaletha, Representations of reductive groups over local fields . . ..... 2948
Joel Kamnitzer, Perfect bases in representation theory: three mountains and their
springs ..... 2976
Yiannis Sakellaridis, Spherical varieties, functoriality, and quantization ..... 2998
Peng Shan, Categorification and applications ..... 3038
Binyong Sun, Chen-Bo Zhu, Theta correspondence and the orbit method ..... 3062
Weiqiang Wang, Quantum symmetric pairs ..... 3080
8. ANALYSIS - SPECIAL LECTURE
Keith Ball, Convex geometry and its connections to harmonic analysis, functional analysis and probability theory ..... 3104
4476
13. COMBINATORICS
Federico Ardila-Mantilla, The geometry of geometries: matroid theory, old and new ..... 4510
Julia Böttcher, Graph and hypergraph packing ..... 4542
Ehud Friedgut, KKL's influence on me ..... 4568
Allen Knutson, Schubert calculus and quiver varieties ..... 4582
Sergey Norin, Recent progress towards Hadwiger's conjecture ..... 4606
Isabella Novik, Face numbers: the upper bound side of the story ..... 4622
Mathias Schacht, Restricted problems in extremal combinatorics ..... 4646
Alex Scott, Graphs of large chromatic number ..... 4660
Asaf Shapira, Local-vs-global combinatorics ..... 4682
Lauren K. Williams, The positive Grassmannian, the amplituhedron, and cluster alge-
bras ..... 4710
14. MATHEMATICS OF COMPUTER SCIENCE - SPECIAL LECTURES
Cynthia Dwork, Differential privacy: getting more for less ..... 4740
Aayush Jain, Huijia Lin, Amit Sahai, Indistinguishability obfuscation ... ..... 4762
David Silver, Andre Barreto, Simulation-based search control ..... 4800
Bernd Sturmfels, Beyond linear algebra ..... 4820
14. MATHEMATICS OF COMPUTER SCIENCE
Roy Gotlib, Tali Kaufman, Nowhere to go but high: a perspective on high-dimensional
expanders ..... 4842
Jelani Nelson, Forty years of frequent items ..... 4872
Oded Regev, Some questions related to the reverse Minkowski theorem ..... 4898
Muli (Shmuel) Safra, Mathematics of computation through the lens of linear equa-
tions and lattices ..... 4914
Ola Svensson, Polyhedral techniques in combinatorial optimization: matchings and
tours ..... 4970
Thomas Vidick, MIP* == RE: a negative resolution to Connes' embedding problem
and Tsirelson's problem ..... 4996
List of contributors ..... 5027
TAMENESS IN GEOMETRY AND ARITHMETIC: BEYOND O-MINIMALITY
GAL BINYAMINI AND DMITRY NOVIKOV
Abstract
The theory of o-minimal structures provides a powerful framework for the study of geometrically tame structures. In the past couple of decades a deep link connecting o-minimality to algebraic and arithmetic geometry has been developing. It has been clear, however, that the axioms of o-minimality do not fully capture some algebro-arithmetic aspects of tameness that one may expect in structures arising from geometry. We propose a notion of sharply o-minimal structures refining the standard axioms of o-minimality, and outline through conjectures and various partial results the potential development of this theory in parallel to the standard one.
The theory of o-minimal structures was introduced by van den Dries as an attempt to provide a framework of tame topology in the spirit of Grothendieck's "Esquisse d'un Programme" [42]. We refer the reader to this book for a general introduction to the subject and its history. For us, an o-minimal structure will always be an expansion of the ordered real field R_("alg "):={R,+,*, < }\mathbb{R}_{\text {alg }}:=\{\mathbb{R},+, \cdot,<\}. Briefly, such an expansion is o-minimal if all definable subsets of R\mathbb{R} consist of finite unions of points and intervals.
Despite their apparent simplicity, it turns out that the axioms of o-minimality provide a broad framework of tame topology. In particular, one has good notions of dimension, smooth stratification, triangulation, and cell-decomposition for every definable set in an o-minimal structure. On the other hand, several natural and important structures turn out to be o-minimal. A few examples of particular importance for us in the present paper are R_(alg),R_(an),R_(an,exp)\mathbb{R}_{\mathrm{alg}}, \mathbb{R}_{\mathrm{an}}, \mathbb{R}_{\mathrm{an}, \mathrm{exp}}, and R_("Pfaff. ")\mathbb{R}_{\text {Pfaff. }}. We will say a bit more on these in later sections.
1.2. Pila-Wilkie counting theorem
In [37], Pila and Wilkie discovered a "counting theorem" that would later find deep applications in arithmetic geometry. The theorem concerns the asymptotic density of rational (or algebraic) points in a definable set-as a function of height. We introduce this first, to motivate a broader discussion of the connection between tame geometry and arithmetic.
For x inQx \in \mathbb{Q}, we denote by H(x)H(x) the standard height of xx. For a vector x inQ^(n)x \in \mathbb{Q}^{n}, we denote by H(x)H(x) the maximum among the heights of the coordinates of xx. For a set A subR^(n)A \subset \mathbb{R}^{n}, we denote the set of Q\mathbb{Q}-points of AA by A(Q)=A nnQ^(n)A(\mathbb{Q})=A \cap \mathbb{Q}^{n} and denote
For a set A subR^(n)A \subset \mathbb{R}^{n}, we define the algebraic part A^("alg ")A^{\text {alg }} of AA to be the union of all connected semialgebraic subsets of AA of positive dimension. We define the transcendental part A^("trans ")A^{\text {trans }} of AA to be A\\A^("alg ")A \backslash A^{\text {alg }}.
Theorem 1 (Pila and Wilkie [37]). Let A subR^(m)A \subset \mathbb{R}^{m} be a set definable in an o-minimal structure. Then for every epsilon > 0\epsilon>0 there exists a constant C(A,epsilon)C(A, \epsilon) such that for every H >= 1H \geqslant 1,
The use of transcendental (as opposed to algebraic) methods in the study of arithmetic questions has a long history. A common theme in these methods, running through the work of Schneider, Lang, Baker, Masser, and Wüstholz to name a few, is the use of auxiliary polynomials. We refer to [28] for a broad treatment of this subject.
The usefulness of polynomials in this context stems from their dual algebraic/analytic role. Suppose one is interested in the set A(Q,H)A(\mathbb{Q}, H) for some analytic set AA. On the one hand, if a polynomial PP, say, with integer coefficients, is evaluated at x in A(Q,H)x \in A(\mathbb{Q}, H) then P(x)P(x) is again rational, and one can estimate its height in terms of HH and the height of PP. On
the other hand, polynomials are extremely well-behaved analytic functions, and a variety of analytic methods may be used to prove upper bounds on the restriction of PP to an analytic set AA assuming it is appropriately constructed (say to vanish to high order at some points of A)A). One concludes from such an argument that PP must vanish at every point in A(Q,H)A(\mathbb{Q}, H), for otherwise the height bound would contradict the upper bound.
The proof of the Pila-Wilkie counting theorem follows this classical line. However, it is fairly unique in the realm of transcendence methods in that the degrees of the auxiliary polynomials PP are independent of the height, depending in fact only on epsi\varepsilon. It is this unusual feature that makes it possible to prove the Pila-Wilkie theorem in the vast generality of o-minimal structures: polynomials of a given degree form a definable family, and the general machinery of o-minimality gives various finiteness statements uniformly for all such polynomials.
1.4. Beyond Pila-Wilkie theorem: the Wilkie conjecture
By contrast with the Pila-Wilkie theorem, most transcendence methods require the degrees of the auxiliary polynomials to depend on the height HH of the points being considered-sometimes logarithmically and in some cases, such as the Schneider-Lang theorem, even linearly. A famous conjecture that seems to fall within this category is due to Wilkie.
Conjecture 2 (Wilkie [37]). Let A subR^(m)A \subset \mathbb{R}^{m} be a set definable in R_(exp)\mathbb{R}_{\exp }. Then there exist constants C(A),kappa(A)C(A), \kappa(A) such that for all H >= 3H \geqslant 3,
The conclusion of the Wilkie conjecture is known to fail for general o-minimal structures, for instance, in R_("an ")\mathbb{R}_{\text {an }} [40]. To achieve such asymptotics, it seems one would have to use auxiliary polynomials of degrees d=(log H)^(q)d=(\log H)^{q}, and o-minimality places no restrictions on the geometric complexity as a function of dd.
In formulating his conjecture, Wilkie was probably influenced by Khovanskii's theory of fewnomials [25]. The latter implies fairly sharp bounds for the number of connected components of sets defined using algebraic and exponential functions (and more generally Pfaffian functions) as a function of the degrees of the equations involved. Below we attempt to axiomatize what it would mean for an arbitrary o-minimal structure to satisfy such sharp complexity bounds.
2. SHARPLY O-MINIMAL STRUCTURES
In this section we introduce sharply o-minimal structures, which are meant to endow a standard o-minimal structure with an appropriate notions comparable to dimension and degree in the algebraic case, and provide suitable control over these parameters under the basic logical operations. We first introduce the notion of a format-degree filtration (abbreviated FDF D-filtration) on a structure SS. This is a collection Omega={Omega_(F,D)}_(F,D inN)\Omega=\left\{\Omega_{\mathcal{F}, D}\right\}_{\mathcal{F}, D \in \mathbb{N}} such that each Omega_(F,D)\Omega_{\mathscr{F}, D} is a collection of definable sets (possibly of different ambient dimensions), with
and uuu_(F,D)Omega\bigcup_{\mathcal{F}, D} \Omega is the collection of all definable sets in S\mathcal{S}. We call the sets in Omega_(F,D)\Omega_{\mathcal{F}, D} sets of format F\mathscr{F} and degree D. However, note that the format and degree of a set are not uniquely defined since Omega\Omega is a filtration rather than a partition.
We now come to the notion of a sharply o-minimal structure.
Definition 3 (Sharply o-minimal structure). A sharply o-minimal structure is a pair Sigma:=(S,Omega)\Sigma:=(S, \Omega) consisting of an o-minimal expansion of the real field SS and an FD-filtration Omega\Omega; and for each FinN\mathscr{F} \in \mathbb{N}, a polynomial P_(F)(*)P_{\mathcal{F}}(\cdot) such that the following holds:
If A inOmega_(F,D)A \in \Omega_{\mathcal{F}, D} then
(1) if A subRA \subset \mathbb{R}, it has at most P_(F)(D)P_{\mathcal{F}}(D) connected components,
(2) if A subR^(â„“)A \subset \mathbb{R}^{\ell} then F >= â„“\mathcal{F} \geqslant \ell,
(3) A^(c),pi_(â„“-1)(A),A xxRA^{c}, \pi_{\ell-1}(A), A \times \mathbb{R}, and Rxx A\mathbb{R} \times A lie in Omega_(F+1,D)\Omega_{\mathscr{F}+1, D}.
Similarly if A_(1),dots,A_(k)subR^(â„“)A_{1}, \ldots, A_{k} \subset \mathbb{R}^{\ell} with A_(j)inOmega_(F_(j),D_(j))A_{j} \in \Omega_{\mathcal{F}_{j}, D_{j}} then
where F:=max_(j)F_(j)\mathscr{F}:=\max _{j} \mathscr{F}_{j} and D=sum_(j)D_(j)D=\sum_{j} D_{j}. Finally,
(6) if P inR[x_(1),dots,x_(â„“)]P \in \mathbb{R}\left[x_{1}, \ldots, x_{\ell}\right] then {P=0}inOmega_(â„“,deg)P\{P=0\} \in \Omega_{\ell, \operatorname{deg}} P.
Given a collection {A_(alpha)}\left\{A_{\alpha}\right\} of sets generating a structure S\mathcal{S}, and associated formats and degrees F_(alpha),D_(alpha)\mathcal{F}_{\alpha}, D_{\alpha} one can consider the minimal FD-filtration Omega\Omega satisfying the axioms (2)-(6) above. We call this the FD-filtration generated by {(A_(alpha),F_(alpha),D_(alpha))}\left\{\left(A_{\alpha}, \mathcal{F}_{\alpha}, D_{\alpha}\right)\right\}. This will be sharply ominimal if and only if axiom (1) is satisfied.
Definition 4 (Reduction of FD-filtrations). Let Omega,Omega^(')\Omega, \Omega^{\prime} be two FD-filtrations on a structure SS. We say that Omega\Omega is reducible to Omega^(')\Omega^{\prime} and write Omega <= Omega^(')\Omega \leqslant \Omega^{\prime} if there exist functions a:NrarrNa: \mathbb{N} \rightarrow \mathbb{N} and b:NrarrN[D]b: \mathbb{N} \rightarrow \mathbb{N}[D] such that
We say that Omega,Omega^(')\Omega, \Omega^{\prime} are equivalent if Omega <= Omega^(') <= Omega\Omega \leqslant \Omega^{\prime} \leqslant \Omega.
We will usually try to prove that certain measures of complexity of definable sets depend polynomially on the degree, thinking of the format as constant. If one can prove such a statement for Omega^(')\Omega^{\prime}-degrees, and Omega <= Omega^(')\Omega \leqslant \Omega^{\prime}, then the same statement holds for Omega\Omega-degrees and in this sense Omega\Omega is reducible to Omega^(')\Omega^{\prime}.
Remark 5 (Effectivity). One can require further that a sharply o-minimal structure is effective, in the sense that the polynomial P_(F)(D)P_{\mathcal{F}}(D) in Definition 3 is given by some explicit primitive recursive function of F\mathscr{F}. Similarly, one may require a reduction Omega <= Omega^(')\Omega \leqslant \Omega^{\prime} to be effective. Unless otherwise stated, all constructions in this paper are effective in this sense.
2.1. Examples and nonexamples
2.1.1. The semialgebraic structure
Consider the structure R_("alg ")\mathbb{R}_{\text {alg }} with the FD-filtration Omega\Omega generated by all algebraic hypersurfaces {P=0}\{P=0\} with the format given by the ambient dimension and the degree given by deg P\operatorname{deg} P. Then (R_("alg "),Omega)\left(\mathbb{R}_{\text {alg }}, \Omega\right) is a sharply o-minimal structure. This is not an immediate statement: it follows from the results on effective cell decomposition, or elimination of quantifiers, in semialgebraic geometry [3][3].
Perhaps a more natural notion of format and degree in the semialgebraic category is as follows. Define Omega_(F,D)^(')\Omega_{\mathcal{F}, D}^{\prime} to be the subsets of R^(â„“)\mathbb{R}^{\ell} with â„“ <= F\ell \leqslant \mathcal{F}, that can be written as a union of basic sets
with the sum of the degrees of the P_(i)P_{i} and Q_(j)Q_{j}, over all basic sets, bounded by DD. This is not sharply o-minimal according to our definition because it does not satisfy axiom (3), for instance. However, it is equivalent to Omega\Omega defined above.
2.1.2. The analytic structure R_("an ")\mathbb{R}_{\text {an }}
Not surprisingly, R_("an ")\mathbb{R}_{\text {an }} is not sharply o-minimal with respect to any FD-filtration. Assume the contrary. Let omega_(1)=1\omega_{1}=1 and omega_(n+1)=2^(omega_(n))\omega_{n+1}=2^{\omega_{n}}, and let Gamma={y=f(z)}subC^(2)\Gamma=\{y=f(z)\} \subset \mathbb{C}^{2} denote the graph of the holomorphic function f(z)=sum_(j=1)^(oo)z^(omega_(j))f(z)=\sum_{j=1}^{\infty} z^{\omega_{j}} restricted to the disc of radius 1//21 / 2 (which is definable in R_(an)\mathbb{R}_{\mathrm{an}} ). Then by axioms (1), (5) and (6), the number of points in
should be polynomial in omega_(n)\omega_{n}, with the exact polynomial depending on the format and degree of Gamma\Gamma. But it is, in fact, omega_(n+1)=2^(omega_(n))\omega_{n+1}=2^{\omega_{n}} for 0 < epsi≪10<\varepsilon \ll 1, and we have a contradiction for n≫1n \gg 1.
2.1.3. Pfaffian structures
Let B subR^(â„“)B \subset \mathbb{R}^{\ell} be a domain, which for simplicity we take to be a product of (possibly infinite) intervals. A tuple f_(1),dots,f_(m):B rarrRf_{1}, \ldots, f_{m}: B \rightarrow \mathbb{R} of analytic functions is called a Pfaffian chain if they satisfy a triangular system of algebraic differential equations of the form
{:(2.5)(delf_(i))/(delx_(j))=P(x_(1),dots,x_(â„“),f_(1),dots,f_(i))","quad AA i","j:}\begin{equation*}
\frac{\partial f_{i}}{\partial x_{j}}=P\left(x_{1}, \ldots, x_{\ell}, f_{1}, \ldots, f_{i}\right), \quad \forall i, j \tag{2.5}
\end{equation*}
They are called restricted if BB is bounded and f_(1),dots,f_(m)f_{1}, \ldots, f_{m} extend as real analytic functions to bar(B)\bar{B}. A Pfaffian function is a polynomial Q(x_(1),dots,x_(â„“),f_(1),dots,f_(m))Q\left(x_{1}, \ldots, x_{\ell}, f_{1}, \ldots, f_{m}\right). We denote the structure generated by the Pfaffian functions by R_("Pfaff ")\mathbb{R}_{\text {Pfaff }}, and its restricted analog by R_(rPfaff)\mathbb{R}_{\mathrm{rPfaff}}.
Khovanskii [25] proved upper bounds for the number of connected components of systems of Pfaffian equations. This was later extended by Gabrielov and Vorobjov to sets defined using inequalities and quantifiers [21]. However, their results fall short of establishing the sharp o-minimality of R_(rPffaff)\mathbb{R}_{\mathrm{rPffaff}}. The problem is that for Gabrielov-Vorobjov's notion of format and degree, if A inOmega_(F,D)A \in \Omega_{\mathscr{F}, D} then they are only able to show that A^(c)inOmega_(P_(F)(D),P_(F)(D))A^{c} \in \Omega_{P_{\mathscr{F}}(D), P_{\mathscr{F}}(D)}
rather than A^(c)inOmega_(F+1,P_(F)(D))A^{c} \in \Omega_{\mathscr{F}+1, P_{\mathscr{F}}(D)} as required by our axioms. This is a fundamental difficulty, as it is essential in our setup that the format never becomes dependent on the degree.
In [13] the first author and Vorobjov introduce a modified notion of format and degree and prove the following.
Theorem 6. There is an FDF D-filtration Omega\Omega on R_(rPfaff)\mathbb{R}_{\mathrm{rPfaff}} that makes it into a sharply o-minimal structure. Moreover, Gabrielov-Vorobjov's standard filtration is reducible to Omega\Omega.
We conjecture that this theorem extends to the structure R_("Pfaff ")\mathbb{R}_{\text {Pfaff }}, and this is the subject of work in progress by the first author and Vorobjov utilizing some additional ideas of Gabrielov [19].
2.2. Cell decomposition in sharply o-minimal structures
We recall the notion of a cell in an o-minimal structure. A cell C subRC \subset \mathbb{R} is either a point or an open interval (possibly infinite). A cell C subR^(â„“+1)C \subset \mathbb{R}^{\ell+1} is either the graph of a definable continuous function f:C^(')rarrRf: C^{\prime} \rightarrow \mathbb{R} where C^(')subR^(â„“)C^{\prime} \subset \mathbb{R}^{\ell} is a cell, or the area strictly between two graphs of such definable continuous functions f,g:C^(')rarrRf, g: C^{\prime} \rightarrow \mathbb{R} satisfying f < gf<g identically on C^(')C^{\prime}. One can also take f=-oof=-\infty and g=oog=\infty in this definition.
We say that a cell C subR^(ℓ)C \subset \mathbb{R}^{\ell} is compatible with X subR^(ℓ)X \subset \mathbb{R}^{\ell} if it is either strictly contained, or strictly disjoint from XX. The following cell decomposition theorem can be viewed as the raison d'être of the axioms of o-minimality.
Theorem 7 (Cell decomposition). Let X_(1),dots,X_(k)subR^(â„“)X_{1}, \ldots, X_{k} \subset \mathbb{R}^{\ell} be definable sets. Then there is a decomposition of R^(â„“)\mathbb{R}^{\ell} into pairwise disjoint cells that are pairwise compatible with X_(1),dots,X_(k)X_{1}, \ldots, X_{k}.
Given the importance of cell decomposition in the theory of o-minimality, it is natural to pose the following question.
Question 8. If SS is sharply o-minimal and X_(1),dots,X_(k)X_{1}, \ldots, X_{k} have format F\mathscr{F} and degree DD, can one find a cell-decomposition where each cell has format const(F)\operatorname{const}(\mathcal{F}), and the number of cells and their degrees are bounded by poly _(F,F)(k,D){ }_{\mathcal{F}, \mathcal{F}}(k, D) ?
We suspect the answer to this question may be negative. Since cell decomposition is perhaps the most crucial construction in o-minimality, this is a fundamental problem. The following result rectifies the situation.
Theorem 9. Let (S,Omega)(\mathcal{S}, \Omega) be sharply o-minimal. Then there exists another FDF D-filtration Omega^(')\Omega^{\prime} with ( S,Omega^(')S, \Omega^{\prime} ) sharply o-minimal such that Omega <= Omega^(')\Omega \leqslant \Omega^{\prime}, and in Omega^(')\Omega^{\prime} the following holds.
Let X_(1),dots,X_(k)inOmega_(F,D)^(')X_{1}, \ldots, X_{k} \in \Omega_{\mathcal{F}, D}^{\prime}, all subsets of R^(â„“)\mathbb{R}^{\ell}. Then there exists a cell decomposition of R^(â„“)\mathbb{R}^{\ell} compatible with each X_(j)X_{j} such that each cell has format const (F)(\mathscr{F}), the number of cells is poly F(k,D)\mathcal{F}(k, D), and the degree of each cell is poly_(F)(D)\operatorname{poly}_{\mathcal{F}}(D).
In the structure R_(rPfaff)\mathbb{R}_{\mathrm{rPfaff}}, Theorem 9 is one of the main results of [13]. The general case is obtained by generalizing the proof to the general sharply o-minimal case, and is part of the PhD\mathrm{PhD} thesis of Binyamin Zack-Kutuzov.
2.3. Yomdin-Gromov algebraic lemma in sharply o-minimal structures
Let I:=(0,1)I:=(0,1). For f:I^(n)rarrR^(m)f: I^{n} \rightarrow \mathbb{R}^{m} a C^(r)C^{r}-smooth map, we denote
The Yomdin-Gromov algebraic lemma is a result about C^(r)C^{r}-smooth parametrizations of bounded norm for definable subsets of I^(n)I^{n}. A sharply o-minimal version of this lemma is as follows.
Lemma 10. Let (S,Omega)(\mathcal{S}, \Omega) be sharply o-minimal. Then there is a polynomial P_(F,r)(*)P_{\mathcal{F}, r}(\cdot) depending on the pair (F,r)(\mathcal{F}, r), such that for every A inOmega_(F,D)A \in \Omega_{\mathcal{F}, D} the following holds. There exist a collection of maps {f_(alpha):I^(n_(alpha))rarr A}\left\{f_{\alpha}: I^{n_{\alpha}} \rightarrow A\right\} of size at most P_(F,r)(D)P_{\mathcal{F}, r}(D) such that uuu_(alpha)f_(alpha)(I^(n_(alpha)))=A\bigcup_{\alpha} f_{\alpha}\left(I^{n_{\alpha}}\right)=A; and ||f_(alpha)||_(r) <= 1\left\|f_{\alpha}\right\|_{r} \leqslant 1 and n_(alpha) <= dim An_{\alpha} \leqslant \operatorname{dim} A for every alpha\alpha.
In the algebraic case, this result is due to Gromov [23], based on a similar but slightly more technically involved statement by Yomdin [44]. In the general o-minimal case, but without complexity bounds, the result is due to Pila and Wilkie [37]. In the restricted Pfaffian case, this result is due to the first author with Jones, Schmidt, and Thomas [6] using Theorem 9 in the R_(rPfaff)\mathbb{R}_{\mathrm{rPfaff}} case. The general case follows in the same way.
The following conjecture seems plausible, though we presently do not have an approach to proving it in this generality.
Conjecture 11. In Lemma 10, one can replace P_(F,r)(D)P_{\mathcal{F}, r}(D) by a P_(F)(D,r)P_{\mathcal{F}}(D, r), i.e., by a polynomial in both DD and rr, depending only on F\mathcal{F}.
In the structure R_("alg ")\mathbb{R}_{\text {alg }} this was conjectured by Yomdin (unpublished) and by Burguet [14], in relation to a conjecture of Yomdin [45, CONJECTURE 6.1] concerning the rate of decay of the tail entropy for real-analytic mappings. The conjecture was proved in [9] by complexanalytic methods. We will say more about the possible generalization of these methods to more general sharply o-minimal structures in Section 3.
2.4. Pila-Wilkie theorem in sharply o-minimal structures
We now state a form of the Pila-Wilkie counting theorem, Theorem 1, with explicit control over the asymptotic constant.
Theorem 12. Let (S,Omega)(S, \Omega) be sharply o-minimal. Then for every epsilon > 0\epsilon>0 and F\mathcal{F} there is a polynomial P_(F,epsilon)(*)P_{\mathcal{F}, \epsilon}(\cdot) depending on (S,Omega)(\mathcal{S}, \Omega), such that for every A inOmega_(F,D)A \in \Omega_{\mathcal{F}, D} and H >= 2H \geqslant 2,
This result is based on Lemma 10, in the same way as the classical Pila-Wilkie theorem is based on the o-minimal reparametrization lemma. This reduction is carried out in [6] using Theorem 9 in the R_(rPfaff)\mathbb{R}_{\mathrm{rPfaff}} case. The general case follows in the same way.
2.5. Polylog counting in sharply o-minimal structures
We state a conjectural sharpening of the Pila-Wilkie theorem, in line with the Wilkie conjecture, in the context of sharply o-minimal structures. For A subR^(â„“)A \subset \mathbb{R}^{\ell}, let
where h(*)h(\cdot) denotes the logarithmic Weil height.
Conjecture 13. Let (S,Omega)(\mathcal{S}, \Omega) be sharply o-minimal. Then there is a polynomial P_(F)(*,*,*)P_{\mathcal{F}}(\cdot, \cdot, \cdot) depending only on (S,Omega)(\mathcal{S}, \Omega) and F\mathcal{F}, such that for every A inOmega_(F,D)A \in \Omega_{\mathcal{F}, D} and g,h >= 2g, h \geqslant 2,
The conjecture sharpens Pila-Wilkie in two ways. First, we replace the subpolynomial term H^(epsi)H^{\varepsilon} by a polynomial in h∼log Hh \sim \log H. Second, we count algebraic points of arbitrary degree, and stipulate polynomial growth with respect to the degree as well.
Conjecture 13 is currently known only for the structure of restricted elementary functions R^(RE):=(R,+,*, < , exp|_([0,1]), sin|_([0,pi]))\mathbb{R}^{\mathbb{R E}}:=\left(\mathbb{R},+, \cdot,<,\left.\exp \right|_{[0,1]},\left.\sin \right|_{[0, \pi]}\right) where it is due to [8][8] (with a minor technical improvement in [5][5] ).
Combining the various known techniques in the literature, it is not hard to see that Conjecture 11 implies Conjecture 13 in a general sharply o-minimal structure. In Section 5 we will see that Conjecture 13 has numerous applications in arithmetic geometry, going beyond the standard applications of the Pila-Wilkie theorem. We also discuss some partial results in the direction of Conjecture 13 in Section 4.4.
3. COMPLEX ANALYTIC THEORY
In this section we consider holomorphic analogs of the standard cell decomposition of o-minimality. We fix a sharply o-minimal structure (S,Omega)(S, \Omega) throughout. We also assume that SS admits cell-decomposition in the sense of Theorem 9 , as we may always reduce to this case.
3.1. Complex cells
We start be defining the notion of a complex cell. This is a complex analog of the cells used in o-minimal geometry.
3.1.1. Basic fibers and their extensions
For r inCr \in \mathbb{C} (resp. r_(1),r_(2)inCr_{1}, r_{2} \in \mathbb{C} ) with |r| > 0|r|>0 (resp. |r_(2)| > |r_(1)| > 0\left|r_{2}\right|>\left|r_{1}\right|>0 ), we denote
For any 0 < rho < oo0<\rho<\infty, we define the {rho}\{\rho\}-extension F{rho}\mathcal{F}\{\rho\} of F\mathcal{F} to be F^(delta)\mathcal{F}^{\delta} where delta\delta satisfies the equations
{:[rho=(2pi delta)/(1-delta^(2))quad" for "F" of type "D],[(3.3)rho=(pi^(2))/(2|log delta|)quad" for "F" of type "D_(@)","D_(oo)","A]:}\begin{align*}
& \rho=\frac{2 \pi \delta}{1-\delta^{2}} \quad \text { for } \mathcal{F} \text { of type } D \\
& \rho=\frac{\pi^{2}}{2|\log \delta|} \quad \text { for } \mathcal{F} \text { of type } D_{\circ}, D_{\infty}, A \tag{3.3}
\end{align*}
The motivation for this notation comes from the following fact, describing the hyperbolic-metric properties of a domain F\mathscr{F} within its {rho}\{\rho\}-extension.
Fact 14. Let F\mathcal{F} be a domain of type A,D,D_(@),D_(oo)A, D, D_{\circ}, D_{\infty} and let SS be a component of the boundary of F\mathcal{F} in F{rho}\mathcal{F}\{\rho\}. Then the length of SS in F{rho}\mathcal{F}\{\rho\} is at most rho\rho.
3.1.2. The definition of a complex cell
Let X,y\mathcal{X}, y be sets and F:X rarr2^(y)\mathcal{F}: X \rightarrow 2^{y} be a map taking points of XX to subsets of yy. Then we denote
{:(3.4)Xo.F:={(x","y):x inX","y inF(x)}.:}\begin{equation*}
\mathcal{X} \odot \mathcal{F}:=\{(x, y): x \in \mathcal{X}, y \in \mathcal{F}(x)\} . \tag{3.4}
\end{equation*}
If r:XrarrC\\{0}r: \mathcal{X} \rightarrow \mathbb{C} \backslash\{0\} then for the purpose of this notation we understand D(r)D(r) as the map assigning to each x inXx \in \mathcal{X} the disc D(r(x))D(r(x)), and similarly for D_(@),D_(oo),AD_{\circ}, D_{\infty}, A.
We now introduce the notion of a complex cell of length â„“inZ_( >= 0)\ell \in \mathbb{Z}_{\geqslant 0}. If U subC^(n)U \subset \mathbb{C}^{n} is a definable domain, we denote by O_(d)(U)\mathcal{O}_{d}(U) the space of definable holomorphic functions on UU. As a shorthand we denote z_(1..â„“)=(z_(1),dots,z_(â„“))\mathbf{z}_{1 . . \ell}=\left(\mathbf{z}_{1}, \ldots, \mathbf{z}_{\ell}\right).
Definition 15 (Complex cells). A complex cell ⨀\bigodot of length zero is the point C^(0)\mathbb{C}^{0}. A com-
and the fiber F\mathscr{F} is one of **,D(r),D_(@)(r),D_(oo)(r),A(r_(1),r_(2))*, D(r), D_{\circ}(r), D_{\infty}(r), A\left(r_{1}, r_{2}\right) where r inO_(d)(C_(1..â„“))r \in \mathcal{O}_{d}\left(\mathscr{C}_{1 . . \ell}\right) satisfies |r(z_(1..â„“))| > 0\left|r\left(\mathbf{z}_{1 . . \ell}\right)\right|>0 for z_(1..â„“)inC_(1..â„“);\mathbf{z}_{1 . . \ell} \in \mathcal{C}_{1 . . \ell} ; and r_(1),r_(2)inO_(d)(C_(1..â„“))r_{1}, r_{2} \in \mathcal{O}_{d}\left(\mathcal{C}_{1 . . \ell}\right) satisfy 0 < |r_(1)(z_(1..â„“))| < |r_(2)(z_(1..â„“))|0<\left|r_{1}\left(\mathbf{z}_{1 . . \ell}\right)\right|<\left|r_{2}\left(\mathbf{z}_{1 . . \ell}\right)\right| for z_(1..â„“)inC_(1.â„“)\mathrm{z}_{1 . . \ell} \in \mathcal{C}_{1 . \ell}.
Next, we define the notion of a delta\delta-extension (resp. {rho}\{\rho\}-extension).
Definition 16. The cell of length zero is defined to be its own delta\delta-extension. A cell varphi\varphi of length ℓ+1\ell+1 admits a delta\delta-extension ⨀delta:=⨀_(1..ℓ)^(delta)o.F^(delta)\bigodot^{\delta}:=\bigodot_{1 . . \ell}^{\delta} \odot \mathscr{F}^{\delta} if C_(1..ℓ)\mathcal{C}_{1 . . \ell} admits a delta\delta-extension, and if the function rr (resp. r_(1),r_(2)r_{1}, r_{2} ) involved in F\mathscr{F} admits holomorphic continuation to C_(1..ℓ)^(delta)\mathcal{C}_{1 . . \ell}^{\delta} and satisfies |r(z_(1..ℓ))| > 0(:}\left|r\left(\mathbf{z}_{1 . . \ell}\right)\right|>0\left(\right. resp. {:0 < |r_(1)(z_(1..ℓ))| < |r_(2)(z_(1..ℓ))|)\left.0<\left|r_{1}\left(\mathbf{z}_{1 . . \ell}\right)\right|<\left|r_{2}\left(\mathbf{z}_{1 . . \ell}\right)\right|\right) in this larger domain. The {rho}\{\rho\}-extension ⨀{rho}\bigodot^{\{\rho\}} is defined in an analogous manner.
As a shorthand, when say that ⨀delta\bigodot^{\delta} is a complex cell (resp. C^({rho})\mathcal{C}^{\{\rho\}} ) we mean that C\mathscr{C} is a complex cell admitting a delta\delta (resp {rho}\{\rho\} ) extension.
3.1.3. The real setting
We introduce the notion of a real complex cell C\mathcal{C}, which we refer to simply as real cells (but note that these are subsets of C^(â„“)\mathbb{C}^{\ell} ). We also define the notion of real part of a real cell C\mathcal{C} (which lies in R^(â„“)\mathbb{R}^{\ell} ), and of a real holomorphic function on a real cell. Below we let R_(+)\mathbb{R}_{+}denote the set of positive real numbers.
Definition 17 (Real complex cells). The cell of length zero is real and equals its real part. A cell C:=C_(1..ℓ)o.F\mathcal{C}:=\mathscr{C}_{1 . . \ell} \odot \mathscr{F} is real if C_(1..ℓ)\mathscr{C}_{1 . . \ell} is real and the radii involved in F\mathscr{F} can be chosen to be real holomorphic functions on ⨀_(1.ℓ)\bigodot_{1 . \ell}; The real part RC\mathbb{R} \mathscr{C} (resp. positive real part R_(+)⨀\mathbb{R}_{+} \bigodot ) of C\mathscr{C} is defined to be RC_(1..ℓ)o.RF\mathbb{R} \mathscr{C}_{1 . . \ell} \odot \mathbb{R} \mathcal{F} (resp. R_(+)C_(1..ℓ)o.R_(+)F\mathbb{R}_{+} \mathscr{C}_{1 . . \ell} \odot \mathbb{R}_{+} \mathscr{F} ) where RF:=FnnR\mathbb{R} \mathscr{F}:=\mathscr{F} \cap \mathbb{R} (resp. R_(+)F:=FnnR_(+)\mathbb{R}_{+} \mathscr{F}:=\mathscr{F} \cap \mathbb{R}_{+}) except the case F=**\mathscr{F}=*, where we set R**=R_(+)**=**\mathbb{R} *=\mathbb{R}_{+} *=*; A holomorphic function on C\mathscr{C} is said to be real if it is real on RC\mathbb{R} \mathcal{C}.
3.2. Cellular parametrization
We now state a result that can be viewed as a complex analog of the cell decomposition theorem. We start by introducing the notion of prepared maps.
Definition 18 (Prepared maps). Let â„“, hat(epsilon)\mathcal{\ell}, \hat{\epsilon} be two cells of length â„“\ell. We say that a holomorphic map f:Crarr hat(e)f: \mathscr{\mathscr { C }} \rightarrow \hat{\mathscr{e}} is prepared if it takes the form w_(j)=z_(j)^(q_(j))+phi_(j)(z_(1..j-1))\mathbf{w}_{j}=\mathbf{z}_{j}^{q_{j}}+\phi_{j}\left(\mathbf{z}_{1 . . j-1}\right) where phi_(j)inO_(d)(C_(1..j))\phi_{j} \in \mathcal{O}_{d}\left(\mathscr{C}_{1 . . j}\right) for j=1,dots,â„“j=1, \ldots, \ell.
Since our cells are always centered at the origin, it is the images of cellular maps that should be viewed as analogous to the cells of o-minimality. The additional exponent q_(j)q_{j} in Definition 18 is needed to handle ramification issues that are not visible in the real context.
Definition 19. For a complex cell C\mathscr{C} and F inO_(d)(C)F \in \mathcal{O}_{d}(\mathscr{C}) we say that FF is compatible with C\mathscr{C} if FF vanishes either identically or nowhere on varphi\varphi. For a cellular map f: hat(ℓ)rarr⨀f: \hat{\ell} \rightarrow \bigodot, we say that ff is compatible with FF if f^(**)Ff^{*} F is compatible with hat(e)\hat{e}.
We will be interested in covering (real) cells by prepared images of (real) cells.
Definition 20. Let ⨀{rho}\bigodot^{\{\rho\}} be a cell and {f_(j):⨀_(j)^({sigma})rarr⨀{rho}}\left\{f_{j}: \bigodot_{j}^{\{\sigma\}} \rightarrow \bigodot^{\{\rho\}}\right\} be a finite collection of cellular maps. We say that this collection is a cellular cover of C\mathscr{C} if Csubuuu_(j)(f_(j)(C_(j)))\mathscr{C} \subset \bigcup_{j}\left(f_{j}\left(\mathscr{C}_{j}\right)\right). Similarly, we say it is a real cellular cover if R_(+)varphi subuuu_(j)(f_(j)(R_(+)⨀_(j)))\mathbb{R}_{+} \varphi \subset \bigcup_{j}\left(f_{j}\left(\mathbb{R}_{+} \bigodot_{j}\right)\right).
Finally, we can state our main conjecture on complex cellular parametrizations.
Conjecture 21 (Cellular Parametrization Theorem, CPT). Let rho,sigma in(0,oo)\rho, \sigma \in(0, \infty). Let ⨀{rho}\bigodot^{\{\rho\}} be a (real) cell and F_(1),dots,F_(M)inO_(d)(⨀{rho})F_{1}, \ldots, F_{M} \in \mathcal{O}_{d}\left(\bigodot^{\{\rho\}}\right) (real) holomorphic functions, with ⨀{rho}\bigodot^{\{\rho\}} and each F_(j)F_{j} having format F\mathcal{F} and degree DD. Then there exists a (real) cellular cover
of cells is poly_(F)(D,M,rho,1//sigma)\operatorname{poly}_{\mathcal{F}}(D, M, \rho, 1 / \sigma), and each of them has format const(F)\operatorname{const}(\mathscr{F}) and degree poly_(F)(D)\operatorname{poly}_{\mathcal{F}}(D).
The main result of [9] is that Conjecture 21 holds in the structure R_("alg ")\mathbb{R}_{\text {alg }} (we assume there for technical convenience that the functions are bounded rather than just definable, but this does not seem to be a serious obstacle). We remark that there are significant difficulties with extending this proof to the general sharply o-minimal case.
3.3. Analytically generated structures
We say that a sharply o-minimal structure (S,Omega)(S, \Omega) is analytically generated if there is a collection of complex cells {C_(alpha)}\left\{\mathcal{C}_{\alpha}\right\} admitting a 1/2-extension, and associated formats and
degrees (F_(alpha),D_(alpha))\left(\mathscr{F}_{\alpha}, D_{\alpha}\right) such that SS is generated by {C_(alpha)}\left\{\mathscr{C}_{\alpha}\right\} and Omega\Omega is generated by {(C_(alpha),F_(alpha),D_(alpha))}\left\{\left(\mathscr{C}_{\alpha}, \mathcal{F}_{\alpha}, D_{\alpha}\right)\right\}. We fix such a structure SS below. Assuming the CPT, one can prove the following analog of Theorem 9 giving a cell decomposition by real parts of complex analytic cells.
Theorem 22. Let (S,Omega)(S, \Omega) be sharply o-minimal and assume that it satisfies the CPT. Then there exists another FDF D-filtration Omega^(')\Omega^{\prime} with (S,Omega^('))\left(\mathcal{S}, \Omega^{\prime}\right) sharply o-minimal such that Omega <= Omega^(')\Omega \leqslant \Omega^{\prime}, and in Omega^(')\Omega^{\prime} the following holds.
Let X_(1),dots,X_(k)inOmega_(F,D)^(')X_{1}, \ldots, X_{k} \in \Omega_{\mathcal{F}, D}^{\prime}, all subsets of R^(â„“)\mathbb{R}^{\ell}. Then there exists a real cellular cover
each X_(i)X_{i}. The number of cells is poly_(F)(D,k,1//sigma)\operatorname{poly}_{\mathcal{F}}(D, k, 1 / \sigma), and each of them has format const(F)\operatorname{const}(\mathcal{F}) and degree poly_(F)(D)\operatorname{poly}_{\mathcal{F}}(D).
In particular, the cells f_(j)(R_(+)⨀_(j))subR^(ℓ)f_{j}\left(\mathbb{R}_{+} \bigodot_{j}\right) \subset \mathbb{R}^{\ell} form a cell-decomposition of R^(ℓ)\mathbb{R}^{\ell} compatible with X_(1),dots,X_(k)X_{1}, \ldots, X_{k}. In addition, each cell admits "analytic continuation" to a complex cell C_(j)\mathscr{C}_{j} with a {sigma}\{\sigma\}-extension.
In [9] it is shown that from a parametrization of the type provided by Theorem 22 one can produce C^(r)C^{r}-smooth parametrizations, with the number of maps depending polynomially on both DD and rr. In particular, the conclusion of Theorem 22 implies Conjectures 11 and 13 . It therefore seems that proving the CPT in a general analytically-generated sharply o-minimal structure provides a plausible approach to these two conjectures.
We remark that a different complex analytic approach, based on the notion of Weierstrass polydiscs, was employed in [8] to prove the Wilkie conjecture in the structure R^(RE)\mathbb{R}^{\mathrm{RE}}. This may also give an approach to proving Conjecture 13 in general, but it does not seem to be applicable to Conjecture 11.
3.4. Complex cells, hyperbolic geometry, and preparation theorems
The main motivation for introduction the notion of {rho}\{\rho\}-extensions of complex cells is that one can use the hyperbolic geometry of C\mathscr{C} inside ⨀{rho}\bigodot^{\{\rho\}} to control the geometry of holomorphic functions defined on complex cells. This is used extensively in the proof of the algebraic CPT in [9], but also gives statements of independent interest. We illustrate two of the main statements.
For any hyperbolic Riemann surface XX, we denote by dist(*,*;X)\operatorname{dist}(\cdot, \cdot ; X) the hyperbolic distance on XX. We use the same notation when X=CX=\mathbb{C} and X=RX=\mathbb{R} to denote the usual Euclidean distance, and when X=CP^(1)X=\mathbb{C} P^{1} to denote the Fubini-Study metric normalized to have diameter 1. For x in Xx \in X and r > 0r>0, we denote by B(x,r;X)B(x, r ; X) the open rr-ball centered at xx in XX. For A sub XA \subset X, we denote by B(A,r;X)B(A, r ; X) the union of rr-balls centered at all points of AA.
Lemma 23 (Fundamental lemma for C\\{0,1}\mathbb{C} \backslash\{0,1\} ). Let ⨀{rho}\bigodot^{\{\rho\}} be a complex cell and let f:e^({rho})rarrC\\{0,1}f: \mathcal{e}^{\{\rho\}} \rightarrow \mathbb{C} \backslash\{0,1\} be holomorphic. Then one of the following holds:
The fundamental lemma for C\\{0,1}\mathbb{C} \backslash\{0,1\} implies the Great Picard Theorem: indeed,
f:D_(@)rarrC\\{0,1}f: D_{\circ} \rightarrow \mathbb{C} \backslash\{0,1\} has an image of small diameter in CP^(1)\mathbb{C} P^{1}, hence is bounded away from some w inCP^(1)w \in \mathbb{C} P^{1}, and it follows elementarily that ff is meromorphic at the origin.
If f:⨀{rho}rarrC\\{0}f: \bigodot^{\{\rho\}} \rightarrow \mathbb{C} \backslash\{0\} is a bounded holomorphic map then we may decompose it as f=z^(alpha(f))*U(z)f=\mathbf{z}^{\alpha(f)} \cdot U(\mathbf{z}), where U:⨀{rho}rarrC\\{0}U: \bigodot^{\{\rho\}} \rightarrow \mathbb{C} \backslash\{0\} is a holomorphic map and the branches of log U:e^({rho})rarrC\log U: \mathscr{e}^{\{\rho\}} \rightarrow \mathbb{C} are univalued. The following lemma shows that UU enjoys strong boundedness properties when restricted to C\mathscr{C}.
Lemma 24 (Monomialization lemma). Let 0 < rho < oo0<\rho<\infty and let f:C^({rho})rarrC\\{0}f: \mathcal{C}^{\{\rho\}} \rightarrow \mathbb{C} \backslash\{0\} be a holomorphic map. If C^({rho}),f inOmega_(F,D)\mathcal{C}^{\{\rho\}}, f \in \Omega_{\mathcal{F}, D} then there exists a polynomial P_(F)(*)P_{\mathcal{F}}(\cdot) such that |alpha(f)| <= P_(F)(D)|\boldsymbol{\alpha}(f)| \leqslant P_{\mathscr{F}}(D) and
The monomialization lemma is proved in this form for the structure R_("alg ")\mathbb{R}_{\text {alg }} in [9], but the proof extends to the general sharply o-minimal case. It is also shown in [9] that the monomialization lemma in combination with the CPT gives an effective version of the subanalytic preparation theorem of Parusinski [33] and Lion-Rolin [26], which is a key technical tool in the theory of the structure R_(an)\mathbb{R}_{\mathrm{an}}.
3.5. Unrestricted exponentials
One of the milestones in the development of o-minimality is Wilkie's theorem on the model-completeness of R_(exp)\mathbb{R}_{\exp } [43], which, together with Khovanskii's theory of fewnomials, established the o-minimality of R_("exp ")\mathbb{R}_{\text {exp }}. Wilkie's methods were later used by van den Dries and Miller to establish the o-minimality of R_("an,exp ")\mathbb{R}_{\text {an,exp }}. This latter structure plays a key role in many of the applications of o-minimality to arithmetic geometry, since it contains the uniformizing maps of (mixed) Shimura varieties restricted to an appropriate fundamental domain. We conjecture a sharply o-minimal version of the theorems of Wilkie and van den Dries, Miller as follows.
Conjecture 25. Let (S,Omega)(S, \Omega) be an analytically generated sharply o-minimal structure. Let S_(exp)\mathcal{S}_{\exp } denote the structure generated by SS and the unrestricted exponential, and let Omega_(exp)\Omega_{\exp } be the FD-filtration of S_(exp)S_{\exp } generated by Omega\Omega and by the graph of the unrestricted exponential (say with format and degree 1). Then ( S_(exp),Omega_(exp)S_{\mathrm{exp}}, \Omega_{\mathrm{exp}} ) is sharply o-minimal.
It is perhaps plausible to make the same conjecture even without the assumption of analytic generation. However, the analytic case appears to be sufficient for all (currently known) applications, and the availability of the tools discussed in this section make the conjecture seem somewhat more amenable in this case. In particular, Lion-Rolin [26] have a geometric approach to the o-minimality of R_(an,exp)\mathbb{R}_{\mathrm{an}, \mathrm{exp}} using the subanalytic preparation theorem as a basic tool. The CPT provides a sharp version of the subanalytic preparation theorem, thus suggesting a possible path to the proof of Conjecture 25.
4. SHARPLY O-MINIMAL STRUCTURES ARISING FROM GEOMETRY
The fundamental motivation for introducing the notion of sharply o-minimal structures is the expectation that structures arising naturally from geometry should indeed be tame in this stronger sense. We start by motivating the discussion with the example of Abel-Jacobi maps, and then state some general conjectures.
4.1. Abel-Jacobi maps
Recall that for CC a compact Riemann surface of genus gg and omega_(1),dots,omega_(g)\omega_{1}, \ldots, \omega_{g} a basis of holomorphic one-forms on CC, there is an associated lattice of periods Lambda subC^(g)\Lambda \subset \mathbb{C}^{g}, a principally polarized abelian variety Jac(C)≃C^(g)//Lambda\operatorname{Jac}(C) \simeq \mathbb{C}^{g} / \Lambda and, for any choice of base point p_(0)in Cp_{0} \in C, an Abel-Jacobi map
To discuss definability properties of u_(C)u_{C}, we choose a semi-algebraic (or even semi-linear) fundamental domain Delta subC^(g)\Delta \subset \mathbb{C}^{g} for the Lambda\Lambda-action and consider u_(C)u_{C} as a map u_(C):C rarr Deltau_{C}: C \rightarrow \Delta.
Proposition 26. There is an analytically generated sharply o-minimal structure where every u_(C)u_{C} is definable.
Indeed, after covering CC by finitely many charts phi_(j):D rarr C\phi_{j}: D \rightarrow C, where phi_(j)\phi_{j} are algebraic maps extending to some neighborhood of bar(D)\bar{D}, it is enough to show that the structure generated by these phi_(j)^(**)u_(C)\phi_{j}^{*} u_{C} is sharply o-minimal. Moreover, it is enough to show instead that the lifts
are definable. Indeed, tilde(u)_(C,j)( bar(D))\tilde{u}_{C, j}(\bar{D}) being compact meets finitely many translates of Delta\Delta, and the further projection C^(g)rarr Delta\mathbb{C}^{g} \rightarrow \Delta restricted to some ball containing tilde(u)_(C,j)(D)\tilde{u}_{C, j}(D) is thus definable in any sharply o-minimal structures (even in R_("alg ")\mathbb{R}_{\text {alg }} ). The sharp o-minimality of the structure generated by all these tilde(u)_(C,j)\tilde{u}_{C, j} follows from Theorem 6 , since these functions, as indefinite integrals of algebraic one-forms, are restricted-Pfaffian (see, e.g., [27] for the elliptic case).
The construction above, however, is not uniform over CC of a given genus. More precisely, while we do have tilde(u)_(j,C)inOmega_(F,D)\tilde{u}_{j, C} \in \Omega_{\mathcal{F}, D} for some uniform F,D\mathcal{F}, D, the number of algebraic charts phi_(j):D rarr C\phi_{j}: D \rightarrow C may tend to infinity as CC approaches the boundary of the moduli space M_(g)\mathcal{M}_{g} of compact genus gg curves. However, we do have the following.
Proposition 27. There is a sharply o-minimal structure where every u_(C)inOmega_(F,D)u_{C} \in \Omega_{\mathcal{F}, D} for some uniform F=F(g)\mathscr{F}=\mathscr{F}(g) and D=D(g)D=D(g).
To prove this, we replace the covering phi_(j):D rarr C\phi_{j}: D \rightarrow C by a covering phi_(j):e_(j)^(1//2)rarr C\phi_{j}: \mathcal{e}_{j}^{1 / 2} \rightarrow C, where each C_(j)\mathscr{C}_{j} is a one-dimensional complex cell and phi_(j)(C_(j))\phi_{j}\left(\mathscr{C}_{j}\right) covers CC. By the removable
and their degrees are poly F(g)\mathscr{F}(g) by the algebraic CPT. Here we use the fact that a genus gg curve can always be realized as an algebraic curve of degree d=poly(g)d=\operatorname{poly}(g). The same
construction as above now shows that each tilde(u)_(C,j):CrarrC^(g)\tilde{u}_{C, j}: \mathcal{C} \rightarrow \mathbb{C}^{g}, if univalued, is restricted Pfaffian of format F=F(g)\mathcal{F}=\mathcal{F}(g) and degree D=poly_(g)(D)D=\operatorname{poly}_{g}(D). In general, we have
where u_(C,j)^(')u_{C, j}^{\prime} is univalued and a_(C,j,k)a_{C, j, k} is the residue of phi_(j)^(**)omega_(k)\phi_{j}^{*} \omega_{k} around the annulus. Since log z\log z, understood for instance as having a branch cut in the negative real line, is restricted Pfaffian with uniform format and degree over every annulus, this proves the general case.
Finally, one should check that the projection C^(g)rarr Delta\mathbb{C}^{g} \rightarrow \Delta, restricted to tilde(phi)_(j)(C_(j))\tilde{\phi}_{j}\left(\mathscr{C}_{j}\right) is definable (say in R_("alg ")\mathbb{R}_{\text {alg }} ) with format and degree depending only on gg. Equivalently, one should check that tilde(phi)_(j)(C_(j))\tilde{\phi}_{j}\left(\mathscr{C}_{j}\right) meets finitely many translates of Delta\Delta, with the number of translates depending only on gg (if tilde(phi)_(j)(C_(j))\tilde{\phi}_{j}\left(\mathscr{C}_{j}\right) is multivalued then one should take one of its branches). This indeed holds, provided that the fundamental domains Delta\Delta are chosen appropriately. It can be deduced, albeit ineffectively, from the definability of theta functions (in both tau\tau and zz ) on an appropriate fundamental domain [34]. In the case g=1g=1, an explicit upper bound for these constants is given in [24].
The appearance of logarithmic factors in (4.3) is the reason that the structure we obtain is not analytically generated. However, the construction does prove the following.
Proposition 28. There is an analytically generated sharply o-minimal structure (S,Omega)(S, \Omega) where every u_(C)in(Omega_(exp))_(F,D)u_{C} \in\left(\Omega_{\mathrm{exp}}\right)_{\mathcal{F}, D} for some uniform F=F(g)\mathcal{F}=\mathscr{F}(g) and D=D(g)D=D(g).
According to Conjecture 25 the structure S_("exp ")S_{\text {exp }} is indeed sharply o-minimal as well, but this remains open.
4.2. Uniformizing maps of abelian varieties
One can essentially repeat the construction above replacing Jac(C)\operatorname{Jac}(C) by an arbitrary (say principally polarized) abelian variety AA of genus gg. We similarly have a map u:A rarr Deltau: A \rightarrow \Delta where Delta subC^(g)\Delta \subset \mathbb{C}^{g} is a semilinear fundamental domain for the period lattice of AA, corresponding to some fixed basis of the holomorphic ones-forms omega_(1),dots,omega_(g)\omega_{1}, \ldots, \omega_{g} on AA. Propositions 26,27 , and 28 extend to this more general context with essentially the same proof.
4.3. Noetherian functions
We have seen in Sections 4.1 and 4.2 that Abel-Jacobi maps and uniformizing maps of abelian varieties live in a sharply o-minimal structure (in fact, uniformly over all curves or abelian varieties of a given genus). This eventually boils down to the fact that the relevant maps are definable in R_(rPfaff)\mathbb{R}_{\mathrm{rPfaff}}. However, we do not believe that all functions arising from geometry are definable in this structure. For instance, we conjecture that the graph of the modular invariant j(tau)j(\tau) restricted to any nonempty domain is not definable in R_(rPfaff)\mathbb{R}_{\mathrm{rPfaff}}. We do not know how to prove this fact, but Freitag [17] has recently at least shown that j(tau)j(\tau) it not itself Pfaffian, on any nonempty domain, as a consequence of the strong minimality of the differential equation satisfied by j(tau)[18]j(\tau)[18].
One natural extension of the notion of Pfaffian functions are the Noetherian functions. Let B subR^(â„“)B \subset \mathbb{R}^{\ell} be a product of finite intervals. A tuple f_(1),dots,f_(m): bar(B)rarrRf_{1}, \ldots, f_{m}: \bar{B} \rightarrow \mathbb{R} of analytic
functions is called a restricted Noetherian chain if they satisfy a system of algebraic differential equations of the form
{:(4.4)(delf_(i))/(delx_(j))=P(x_(1),dots,x_(â„“),f_(1),dots,f_(m))","quad AA i","j:}\begin{equation*}
\frac{\partial f_{i}}{\partial x_{j}}=P\left(x_{1}, \ldots, x_{\ell}, f_{1}, \ldots, f_{m}\right), \quad \forall i, j \tag{4.4}
\end{equation*}
We denote the structure generated by the restricted Noetherian functions by R_(r" Noether ")\mathbb{R}_{r \text { Noether }}. Since all restricted Noetherian functions are restricted analytic, R_(rNoether)\mathbb{R}_{\mathrm{rNoether}} is o-minimal.
Conjecture 29. The structure R_(rNoether)\mathbb{R}_{\mathrm{r} N o e t h e r ~} is sharply o-minimal with respect to some FD. filtration.
Gabrielov and Khovanskii have considered some local analogs of the theory of fewnomials for nondegenerate systems of Noetherian equations in [20], and made some (still local) conjectures about the general case. These conjectures are proved in [7] under a technical condition. However, these results are all local, bounding the number of zeros in some sufficiently small ball.
Despite the general Conjecture 29 being open, an effective Pila-Wilkie counting theorem was obtained in [4] for semi-Noetherian sets.
Theorem 30. Let A be defined by finitely many restricted Noetherian equalities and inequalities. Then for every epsi > 0\varepsilon>0, we have
where C_(g,A)C_{g, A} can be computed explicitly from the data defining AA.
Of course, provided Conjecture 29 an effective Pila-Wilkie theorem with better bounds (for instance, polynomial in the degree of AA ) would follow from Theorem 12. More generally, as a consequence of Conjecture 13 we would expect sharper polylogarithmic bounds as well. Some results in this direction are discussed in the following section.
4.4. Bezout-type theorems and point counting with foliations
One can think of the graphs of Noetherian functions equivalently as leafs of algebraic foliations. Partial results in the direction of Conjecture 29 have been obtained in [5] in this language. To state the result we consider an ambient quasi-projective variety M\mathbb{M} and a nonsingular mm-dimensional foliation F\mathscr{F} of M\mathbb{M}, both defined over bar(Q)\overline{\mathbb{Q}}. For p inMp \in \mathbb{M} denote by L_(p)\mathscr{L}_{p} the germ of the leaf passing through pp. For a pure-dimensional variety V subMV \subset \mathbb{M}, denote
If VV is defined over bar(Q)\overline{\mathbb{Q}}, we denote by delta_(V)\delta_{V} the sum of the degree deg V\operatorname{deg} V, the log-height h(V)h(V), and the degree of the field of definition of VV over Q\mathbb{Q}. Here the log-height is taken, for instance, to be the log-height of the point representing VV in an appropriate Chow variety. In terms of this data we have the following Bezout-type theorem.
Theorem 31 ([5, THEOREM 1]). Let V subMV \subset \mathbb{M} be defined over a number field and suppose codim_(M)V=m\operatorname{codim}_{M} V=m. Let KK be a compact subset of a leaf of F\mathcal{F}. Then
In fact, the bound in Theorem 31 can be made more explicit giving the precise dependence on F\mathscr{F} and on KK, and this is important in some applications, but we omit the details for brevity. The same bound without the dependence on h(V)h(V) and log dist^(-1)(K,Sigma_(V))\log \operatorname{dist}^{-1}\left(K, \Sigma_{V}\right) would be a consequence of Conjecture 29, and establishing such a bound is probably the main step toward proving the conjecture.
As a consequence of Theorem 31 one can deduce some polylogarithmic pointcounting results in the spirit of Conjecture 13. We state the simplest result of this type for illustration below.
Theorem 32 ([5, corolLARY 6]). Suppose L_(p)\mathscr{L}_{p} contains no germs of algebraic curves, for any p inMp \in \mathbb{M}. Let KK be a compact subset of a leaf of F\mathcal{F}. Then
Once again, the dependence on KK can be made explicit in terms of the foliation F\mathcal{F} and this plays a role in some applications. In practice, Theorem 32 and its more refined forms can be used to deduce the conclusion of Conjecture 13 in most arithmetic applications, since the sets appearing in such applications are always defined in terms of leafs of some highly symmetric foliations.
4.5. Q-functions
Many important functions arising from geometry, such as period integrals, are Noetherian. Indeed, such functions arise as horizontal sections of the Gauss-Manin connection and can thus be viewed as solutions of a linear systems of differential equations. However, the structure R_(rNoether)\mathbb{R}_{\mathrm{rNoether}} only contains the restrictions of such maps to compact domains. If we consider general Noetherian functions on noncompact domains, the result would not even be o-minimal (as illustrated by the sine and cosine functions, for instance). If one is to obtain an o-minimal structure, one must restrict singularities at the boundary.
One candidate class is provided by the notion of QQ-functions considered in [10,11] Let P subC^(n)P \subset \mathbb{C}^{n} be a polydisc, Sigma subC^(n)\Sigma \subset \mathbb{C}^{n} a union of coordinate hyperplanes, and grad\nabla the connection on P xxC^(â„“)P \times \mathbb{C}^{\ell} given by
{:(4.9)grad v=dv-A*v:}\begin{equation*}
\nabla v=\mathrm{d} v-A \cdot v \tag{4.9}
\end{equation*}
where AA is a matrix of one-forms holomorphic in bar(P)\\Sigma\bar{P} \backslash \Sigma. Suppose that the entries of AA are algebraic and defined over bar(Q)\bar{Q}, that grad\nabla has regular singularities along Sigma\Sigma, and that the monodromy of grad\nabla is quasiunipotent. Finally, let P^(@)P^{\circ} be a simply-connected domain obtained by removing from P\\SigmaP \backslash \Sigma a branch cut {Arg x_(i)=alpha_(i)}\left\{\operatorname{Arg} x_{i}=\alpha_{i}\right\} for each of the components {x_(i)=0}\left\{x_{i}=0\right\} of Sigma\Sigma and for some choice of alpha_(i)inR\alpha_{i} \in \mathbb{R} mod 2pi2 \pi. Every solution of grad v=0\nabla v=0 extends as a holomorphic vector-valued function in P^(@)P^{\circ}. We call each component of such a function a Q\mathrm{Q}-function. Denote by R_(QF)\mathbb{R}_{\mathrm{QF}} the structure generated by all such Q\mathrm{Q}-functions. This structure contains, as sections of the Gauss-Manin connection, all period integrals of algebraic families.
By the classical theory of regular-singular linear equations, every Q\mathrm{Q}-function is definable in R_(an,exp)\mathbb{R}_{\mathrm{an}, \exp }, and R_(QF)\mathbb{R}_{\mathrm{QF}} is thus o-minimal.
Conjecture 33. The structure R_(QF)\mathbb{R}_{\mathrm{QF}} is sharply o-minimal with respect to some FD-filtration.
Some initial motivation for Conjecture 33 is provided by the results of [10], which give effective bounds for the number of zeros of QQ-functions restricted to any algebraic curve in PP. However, treating systems of equations in several variables, and obtaining sharp bounds with respect to degrees, is still widely open.
5. APPLICATIONS IN ARITHMETIC GEOMETRY
In this section we describe some applications of sharply o-minimal structures in arithmetic geometry. For some of these, Theorem 12 suffices, while for others Conjecture 13 is necessary-in some suitable sharply o-minimal structure, such as the one conjectured to exist in Conjecture 33. However, in all cases discussed below one can actually carry out the strategy using known results, mostly Theorem 32 and its generalizations, in place of these general conjectures (though various technical difficulties must be resolved in each case). We thus hope to convince the reader that the strategy laid out below is feasible, on the one hand, and fits coherently into the general framework of sharply o-minimal structures, on the other.
5.1. Geometry governs arithmetic
Geometry governs arithmetic describes a general phenomenon in the interaction between geometry (for instance, algebraic geometry) and arithmetic: namely, that arithmetic problems often admit finitely many solutions unless there is an underlying geometric reason to expect infinitely many. Perhaps the most famous example is given by Mordell's conjecture, now Falting's theorem [16]: an algebraic curve C subP^(2)C \subset \mathbb{P}^{2} contains finitely many rational points, unless it is rational or elliptic. The two exceptions in Falting's theorem may be viewed as geometric obstructions to the finitude of rational solutions: the rational parametrization in the former, and the group law in the latter, are geometric mechanisms that can produce infinitely many rational points on the curve.
Below we briefly explain the Pila-Zannier strategy in the Manin-Mumford case. Let AA be an abelian variety and V sub AV \subset A an algebraic subvariety containing no cosets of abelian subvarieties, both defined over a number field K\mathbb{K}.
Let pi:[0,1]^(2g)rarr A\pi:[0,1]^{2 g} \rightarrow A be the universal covering map of AA written in period coordinates, so that rational points with common denominator NN in [0,1]^(2g)[0,1]^{2 g} correspond to NN torsion points in AA. One checks that under our assumptions, X:=pi^(-1)(V)X:=\pi^{-1}(V) has no algebraic part (this can be done with the help of the Pila-Wilkie theorem as well, following a strategy of Pila in [35]). The Pila-Wilkie theorem then implies that the number of torsion points in VV is at most C(X,epsi)N^(epsi)C(X, \varepsilon) N^{\varepsilon} where C(X,epsi)C(X, \varepsilon) is the Pila-Wilkie constant.
On the other hand, there is c > 0c>0 such that if p in Ap \in A is an NN-torsion point then [Q(p):Q]≫_(A)N^(c)[\mathbb{Q}(p): \mathbb{Q}] \gg_{A} N^{c} by a result of David [15]. Here the implied constant depends effectively on AA. This is an example of a Galois lower bound, which in the Pila-Zannier strategy plays the yin to Pila-Wilkie's yang.
Choose epsi=c//2\varepsilon=c / 2 and suppose that VV contains an NN-torsion point pp. Then it contains a fraction of [K:Q]^(-1)[\mathbb{K}: \mathbb{Q}]^{-1} of its Galois conjugates, and we obtain a contradiction as soon as N≫_(A,V)C(X,epsi//2)^(2//c)N \gg_{A, V} C(X, \varepsilon / 2)^{2 / c}. We thus proved a bound for the order of any torsion point in VV, and in particular the finiteness of the set of torsion points.
5.3. Point counting and Galois lower bounds
Traditionally in the Pila-Zannier strategy, the Pila-Wilkie theorem is used to obtain an upper bound on the number of special points, while the competing Galois lower bounds are obtained using other methods-usually involving a combination of height estimates and transcendence methods, such as the results of David [15] or Masser-Wüstholz [29].
In [39] Schmidt suggested an alternative approach to proving Galois lower bounds, replacing the more traditional transcendence methods by polylogarithmic counting results as in Conjecture 13. We illustrate again in the Manin-Mumford setting. Let AA be an abelian variety over a number field K\mathbb{K} and let p in Ap \in A be a torsion point. Consider now XX given by the graph of the map pi\pi defined in the previous section, which is easily seen to contain no algebraic part. The points p,2p,dots,Npp, 2 p, \ldots, N p correspond to NN points x_(1),dots,x_(n)x_{1}, \ldots, x_{n} on this graph. Recall that the height of a torsion point in AA is O_(A)(1)O_{A}(1) (since the Neron-Tate height is zero), and the height of the corresponding point in [0,1]^(2g)[0,1]^{2 g} is at most NN. It follows that h(x_(j))≪A log Nh\left(x_{j}\right) \ll A \log N. On the other hand, the field of definition of each x_(j)x_{j} is, by the product law of AA, contained in K(p)\mathbb{K}(p). We thus have
by Conjecture 13 , and this readily implies [Q(p):Q]≫_(A)N^(c)[\mathbb{Q}(p): \mathbb{Q}] \gg_{A} N^{c} for some c > 0c>0, giving a new proof of the Galois lower bound for torsion points-and with it a "purely point-counting" proof of Manin-Mumford. This has been carried out in [5] using Theorem 32.
The main novelty of this strategy is that it applies in contexts where we have polylog counting result, and where the more traditional transcendence techniques are not available. In [12] this idea was applied in the context of a general Shimura variety SS. It is shown that if
the special points p in Sp \in S satisfy a discriminant-negligible height bound
In the case of the Siegel modular variety S=A_(g)S=\mathscr{A}_{g}, the height bound (5.2) was proved by Tsimerman [41] as a simple consequence of the recently proven averaged Colmez formula [1,46]. Tsimerman deduces the corresponding Galois bound from this using MasserWüstholz' isogeny estimates [29]. However, these estimates are proved using transcendence methods applied to abelian functions, and have no known counterpart applicable when the Shimura variety SS does not parameterize abelian varieties (i.e., is not of abelian type). The result of [12] removes this obstruction.
This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No. 1167/17). This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 802107).
REFERENCES
[1] F. Andreatta, E. Z. Goren, B. Howard, and K. Madapusi Pera, Faltings heights of abelian varieties with complex multiplication. Ann. of Math. (2) 187 (2018), no. 2, 391-531.
[2] F. Barroero and L. Capuano, Unlikely intersections in families of abelian varieties and the polynomial Pell equation. Proc. Lond. Math. Soc. (3) 120 (2020), no. 2, 192-219.
[3] S. Basu, R. Pollack, and M.-F. Roy, Algorithms in real algebraic geometry. Second edn. Algorithms Comput. Math. 10, Springer, Berlin, 2006.
[4] G. Binyamini, Density of algebraic points on Noetherian varieties. Geom. Funct. Anal. 29 (2019), no. 1, 72-118.
[5] G. Binyamini, Point counting for foliations over number fields. 2020, arXiv:2009.00892.
[6] G. Binyamini, G. Jones, H. Schmidt, and M. Thomas, Effective Pila-Wilkie in the restricted sub-Pffafian structure (in preparation).
[7] G. Binyamini and D. Novikov, Multiplicities of Noetherian deformations. Geom. Funct. Anal. 25 (2015), no. 5, 1413-1439.
[8] G. Binyamini and D. Novikov, Wilkie's conjecture for restricted elementary functions. Ann. of Math. (2) 186 (2017), no. 1, 237-275.
[9] G. Binyamini and D. Novikov, Complex cellular structures. Ann. of Math. (2) 190 (2019), no. 1, 145-248.
[10] G. Binyamini, D. Novikov, and S. Yakovenko, On the number of zeros of Abelian integrals. Invent. Math. 181 (2010), no. 2, 227-289.
[11] G. Binyamini, D. Novikov, and S. Yakovenko, Quasialgebraic functions. In Algebraic methods in dynamical systems, pp. 61-81, Banach Center Publ. 94, Polish Acad. Sci. Inst. Math, Warsaw, 2011.
[12] G. Binyamini, H. Schmidt, and A. Yafaev, Lower bounds for Galois orbits of special points on Shimura varieties: a point-counting approach. 2021, arXiv:2104.05842.
[13] G. Binyamini and N. Vorobjov, Effective cylindrical cell decompositions for restricted sub-Pfaffian sets. Int. Math. Res. Not. IMRN (2020); rnaa285, DOI 10.1093/imrn/rnaa285.
[14] D. Burguet, A proof of Yomdin-Gromov's algebraic lemma. Israel J. Math. 168 (2008), 291-316.
[17] J. Freitag, Not Pfaffian. 2021, arXiv:2109.09230.
[18] J. Freitag and T. Scanlon, Strong minimality and the jj-function. J. Eur. Math. Soc. (JEMS) 20 (2018), no. 1, 119-136.
[19] A. Gabrielov, Relative closure and the complexity of Pfaffian elimination. In Discrete and computational geometry, pp. 441-460, Algorithms Combin. 25, Springer, Berlin, 2003.
[20] A. Gabrielov and A. Khovanskii, Multiplicity of a Noetherian intersection. In Geometry of differential equations, pp. 119-130, Amer. Math. Soc. Transl. Ser. 2 186, Amer. Math. Soc., Providence, RI, 1998.
[21] A. Gabrielov and N. Vorobjov, Complexity of computations with Pfaffian and Noetherian functions. In Normal forms, bifurcations and finiteness problems in differential equations, pp. 211-250, NATO Sci. Ser. II Math. Phys. Chem. 137, Kluwer Acad. Publ., Dordrecht, 2004.
[27] A. Macintyre, Some observations about the real and imaginary parts of complex Pfaffian functions. In Model theory with applications to algebra and analysis. Vol. 1, pp. 215-223, London Math. Soc. Lecture Note Ser. 349, Cambridge Univ. Press, Cambridge, 2008.
[28] D. Masser, Auxiliary polynomials in number theory. Cambridge Tracts in Math. 207, Cambridge University Press, Cambridge, 2016.
[29] D. Masser and G. Wüstholz, Isogeny estimates for abelian varieties, and finiteness theorems. Ann. of Math. (2) 137 (1993), no. 3, 459-472.
[30] D. Masser and U. Zannier, Torsion anomalous points and families of elliptic curves. Amer. J. Math. 132 (2010), no. 6, 1677-1691.
[31] D. Masser and U. Zannier, Torsion points on families of simple abelian surfaces and Pell's equation over polynomial rings. J. Eur. Math. Soc. (JEMS) 17 (2015), no. 9, 2379-2416.
[32] D. Masser and U. Zannier, Torsion points, Pell's equation, and integration in elementary terms. Acta Math. 225 (2020), no. 2, 227-313.
[34] Y. Peterzil and S. Starchenko, Definability of restricted theta functions and families of abelian varieties. Duke Math. J. 162 (2013), no. 4, 731-765.
[37] J. Pila and A. J. Wilkie, The rational points of a definable set. Duke Math. J. 133 (2006), no. 3, 591-616.
[38] J. Pila and U. Zannier, Rational points in periodic analytic sets and the ManinMumford conjecture. Atti Accad. Naz. Lincei Rend. Lincei Mat. Appl. 19 (2008), no. 2, 149-162.
[39] H. Schmidt, Counting rational points and lower bounds for Galois orbits. Atti Accad. Naz. Lincei Rend. Lincei Mat. Appl. 30 (2019), no. 3, 497-509.
[42] L. van den Dries, Tame topology and o-minimal structures. London Math. Soc. Lecture Note Ser. 248, Cambridge University Press, Cambridge, 1998.
[43] A. J. Wilkie, Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function. J. Amer. Math. Soc. 9 (1996), no. 4, 1051-1094.
[44] Y. Yomdin, Volume growth and entropy. Israel J. Math. 57 (1987), no. 3, 285-300.
[45] Y. Yomdin, Local complexity growth for iterations of real analytic mappings and semicontinuity moduli of the entropy. Ergodic Theory Dynam. Systems 11 (1991), no. 3, 583-602.
[46] X. Yuan and S.-W. Zhang, On the averaged Colmez conjecture. Ann. of Math. (2) 187 (2018), no. 2, 533-638.
GAL BINYAMINI
Weizmann Institute of Science, Rehovot, Israel, gal.binyamini @ weizmann.ac.il
DMITRY NOVIKOV
Weizmann Institute of Science, Rehovot, Israel, dmitry.novikov @ weizmann.ac.il
RAMSEY THEORY OF HOMOGENEOUS STRUCTURES: CURRENT TRENDS AND OPEN PROBLEMS
NATASHA DOBRINEN
This paper is dedicated to Norbert Sauer for his seminal works on the partition theory of homogeneous structures, and for his mathematical and personal generosity.
Abstract
This article highlights historical achievements in the partition theory of countable homogeneous relational structures, and presents recent work, current trends, and open problems. Exciting recent developments include new methods involving logic, topological Ramsey spaces, and category theory. The paper concentrates on big Ramsey degrees, presenting their essential structure where known and outlining areas for further development. Cognate areas, including infinite dimensional Ramsey theory of homogeneous structures and partition theory of uncountable structures, are also discussed.
Ramsey theory, homogeneous structure, big Ramsey degree, coding tree
1. INTRODUCTION
Ramsey theory is a beautiful subject which interrelates with a multitude of mathematical fields. In particular, since its inception, developments in Ramsey theory have often been motivated by problems in logic; in turn, Ramsey theory has instigated some seminal developments in logic. The intent of this article is to provide the general mathematician with an introduction to the intriguing subject of Ramsey theory on homogeneous structures while being detailed enough to describe the state-of-the-art and the main ideas at play. We present historical highlights and discuss why solutions to problems on homogeneous structures require more than just straightforward applications of finite structural Ramsey theory. In the following sections, we map out collections of recent results and methods which were developed to overcome obstacles associated with forbidden substructures. These new methods involve applications from logic (especially forcing but also ideas from model theory), topological Ramsey spaces, and category theory.
The subject of Ramsey theory on infinite structures begins with this lovely theorem.
Theorem 1.1 (Ramsey, [58]). Given positive integers kk and rr and a coloring of the kk-element subsets of the natural numbers N\mathbb{N} into rr colors, there is an infinite set of natural numbers N subeNN \subseteq \mathbb{N} such that all kk-element subsets of NN have the same color.
There are two natural interpretations of Ramsey's theorem in terms of infinite structures. First, letting << denote the standard linear order on N\mathbb{N}, Ramsey's theorem shows that given any finite coloring of all linearly ordered substructures of (N, < )(\mathbb{N},<) of size kk, there is an isomorphic substructure (N, < )(N,<) of (N, < )(\mathbb{N},<) such that all linearly ordered substructures of (N, < )(N,<) of size kk have the same color. Second, one may think of the kk-element subsets of N\mathbb{N} as kk-hyperedges. Then Ramsey's theorem yields that, given any finite coloring of the kk-hyperedges of the complete kk-regular hypergraph on infinitely many vertices, there is an isomorphic subgraph in which all kk-hyperedges have the same color.
Given this, one might naturally wonder about other structures.
Question 1.2. Which infinite structures carry an analogue of Ramsey's theorem?
The rational numbers (Q, < )(\mathbb{Q},<) as a dense linearly ordered structure (without endpoints) was the earliest test case. It is a fun exercise to show that given any coloring of the rational numbers into finitely many colors, there is one color-class which contains a dense linear order, that is, an isomorphic subcopy of the rationals in one color. Thus, the rationals satisfy a structural pigeonhole principle known as indivisibility.
The direct analogy with Ramsey's theorem ends, however, when we consider pairs of rationals. It follows from the work of Sierpinski in [65] that there is a coloring of the pairs of rationals into two colors so that both colors persist in every isomorphic subcopy of the rationals. Sierpiński's coloring provides a clear understanding of one of the fundamental issues arising in partition theory of infinite structures not occurring in finite structural Ramsey theory. Let {q_(i):i inN}\left\{q_{i}: i \in \mathbb{N}\right\} be a listing of the rational numbers, without repetition, and for i < ji<j define c({q_(i),q_(j)})=c\left(\left\{q_{i}, q_{j}\right\}\right)= blue if q_(i) < q_(j)q_{i}<q_{j}, and c({q_(i),q_(j)})=c\left(\left\{q_{i}, q_{j}\right\}\right)= red if q_(j) < q_(i)q_{j}<q_{i}. Then in
each subset Q subeQQ \subseteq \mathbb{Q} forming a dense linear order, both color classes persist; that is, there are pairs of rationals in QQ colored red and also pairs of rationals in QQ colored blue. Since it is impossible to find an isomorphic subcopy of the rationals in which all pairsets have the same color, a direct analogue of Ramsey's theorem does not hold for the rationals.
The failure of the straightforward analogue of Ramsey's theorem is not the end, but rather just the beginning of the story. Galvin (unpublished) showed a few decades later that there is a bound on the number of unavoidable colors: Given any coloring of the pairs of rationals into finitely many colors, there is a subcopy of the rationals in which all pairs belong to the union of two color classes. Now one sees that Question 1.2 ought to be refined.
Question 1.3. For which infinite structures S\mathbf{S} is there a Ramsey-analogue in the following sense: Let A\mathbf{A} be a finite substructure of S\mathbf{S}. Is there a positive integer TT such that for any coloring of the copies of A\mathbf{A} into finitely many colors, there is a subcopy S^(')\mathbf{S}^{\prime} of S\mathbf{S} in which there are no more than TT many colors for the copies of A\mathbf{A} ?
The least such integer TT, when it exists, is denoted TT (A) and called the big Ramsey degree of A\mathbf{A} in S, a term coined in Kechris-Pestov-Todorcevic (2005). The "big" refers to the fact that we require an isomorphic subcopy of an infinite structure in which the number of colors is as small as possible (in contrast to the concept of small Ramsey degree in finite structural Ramsey theory).
Notice how Sierpiński played the enumeration {q_(i):i inN}\left\{q_{i}: i \in \mathbb{N}\right\} of the rationals against the dense linear order to construct a coloring of pairsets of rationals into two colors, each of which persists in every subcopy of the rationals. This simple, but deep idea sheds light on a fundamental difference between finite and infinite structural Ramsey theory. The interplay between the enumeration and the relations on an infinite structure has bearing on the number of colors that must persist in any subcopy of that structure. We will see examples of this at work throughout this article and explain the general principles which have been found for certain classes of structures with relations of arity at most two, even as the subject aims towards a future overarching theory of big Ramsey degrees.
2. THE QUESTIONS
Given a finite relational language L={R_(i):i < k}\mathscr{L}=\left\{R_{i}: i<k\right\} with each relation symbol R_(i)R_{i} of some finite arity, say, n_(i)n_{i}, an L\mathscr{L}-structure is a tuple A=(:A,R_(0)^(A),dots,R_(k-1)^(A):)\mathbf{A}=\left\langle A, R_{0}^{\mathbf{A}}, \ldots, R_{k-1}^{\mathbf{A}}\right\rangle, where A!=O/A \neq \emptyset is the universe of A\mathbf{A} and for each i < k,R_(i)^(A)subeA^(n_(i))i<k, R_{i}^{\mathbf{A}} \subseteq A^{n_{i}}. For L\mathscr{L}-structures A\mathbf{A} and B\mathbf{B}, an embedding from A\mathbf{A} into B\mathbf{B} is an injection e:A rarr Be: A \rightarrow B such that for all i < k,R_(i)^(A)(a_(1),dots,a_(n_(i)))harri<k, R_{i}^{\mathbf{A}}\left(a_{1}, \ldots, a_{n_{i}}\right) \leftrightarrowR_(i)^(B)(e(a_(1)),dots,e(a_(n_(i))))R_{i}^{\mathbf{B}}\left(e\left(a_{1}\right), \ldots, e\left(a_{n_{i}}\right)\right). The ee-image of A\mathbf{A} is a copy of A\mathbf{A} in B\mathbf{B}. If ee is the identity map, then A\mathbf{A} is a substructure of B\mathbf{B}. An isomorphism is an embedding which is onto its image. We write A <= B\mathbf{A} \leq \mathbf{B} exactly when there is an embedding of A\mathbf{A} into B\mathbf{B}, and A~=B\mathbf{A} \cong \mathbf{B} exactly when A\mathbf{A} and B\mathbf{B} are isomorphic.
Let A,B,C\mathbf{A}, \mathbf{B}, \mathbf{C} be L\mathscr{L}-structures such that A <= B <= C\mathbf{A} \leq \mathbf{B} \leq \mathbf{C}. We use ((B)/(A))\binom{\mathbf{B}}{\mathbf{A}} to denote the set of all copies of A\mathbf{A} in B\mathbf{B}. The Erdós - Rado arrow notation Crarr(B)_(k)^(A)\mathbf{C} \rightarrow(\mathbf{B})_{k}^{\mathbf{A}} means that for each coloring of ((C)/(A))\binom{\mathbf{C}}{\mathbf{A}} into kk colors, there is a B^(')in((C)/(B))\mathbf{B}^{\prime} \in\binom{\mathbf{C}}{\mathbf{B}} such that ([B_(B)^(A)])\left(\begin{array}{l}\mathbf{B}_{\mathbf{B}}^{\mathbf{A}}\end{array}\right) is monochromatic, meaning every member of ((B^('))/(A))\binom{\mathbf{B}^{\prime}}{\mathbf{A}} has the same color.
We say that S\mathbf{S} has finite big Ramsey degrees if TT (A) exists for each finite substructure A of S\mathbf{S}. We say that exact big Ramsey degrees are known if there is either a computation of the degrees or a characterization from which they can be computed. Indivisibility holds if T(A)=1T(\mathbf{A})=1 for each one-element substructure A\mathbf{A} of S\mathbf{S}. The following questions progress in order of strength: A positive answer to (3) implies a positive answer to (2), which in turn implies a positive answer to (1).
Question 2.3. Given a homogeneous structure K\mathbf{K},
(1) Does K\mathbf{K} have finite big Ramsey degrees? That is, can one find upper bounds ensuring that big Ramsey degrees exist?
(2) If K\mathbf{K} has finite big Ramsey degrees, is there a characterization of the exact big Ramsey degrees via canonical partitions? If yes, calculate or find an algorithm to calculate them.
(3) Does K\mathbf{K} carry a big Ramsey structure?
Part (2) of this question involves finding canonical partitions.
Canonical partitions recover an exact analogue of Ramsey's theorem for each piece of the partition. In practice such partitions are characterized by adding extra structure to K\mathbf{K}, including the enumeration of the universe of K\mathbf{K} and a tree-like structure capturing the relations of K\mathbf{K} against the enumeration.
Part (3) of Question 2.3 has to do with a connection between big Ramsey degrees and topological dynamics, in the spirit of the Kechris-Pestov-Todorcevic correspondence, proved by Zucker in [70]. A big Ramsey structure is essentially a finite expansion K^(**)\mathbf{K}^{*} of K\mathbf{K} so that each finite substructure of K^(**)\mathbf{K}^{*} has big Ramsey degree one, and, moreover, the unavoidable colorings cohere in that for A,Bin\mathbf{A}, \mathbf{B} \in Age (K)(\mathbf{K}) with A\mathbf{A} embedding into B\mathbf{B}, the canonical partition for copies of B\mathbf{B} when restricted to copies of A\mathbf{A} recovers the canonical partition for
copies of A. Big Ramsey structures imply canonical partitions. The reverse is not known in general, but certain types of canonical partitions are known to imply big Ramsey structures (Theorem 6.10 in [8]), and it seems reasonable to the author to expect that (1)-(3) are equivalent.
Canonical partitions and big Ramsey structures are really getting at the question of whether we can find an optimal finite expansion K^(**)\mathbf{K}^{*} of a given homogeneous structure K\mathbf{K} so that K^(**)\mathbf{K}^{*} carries an exact analogue of Ramsey's theorem. In this sense, big Ramsey degrees are not quite so mysterious, but are rather saying that an exact analogue of Ramsey's theorem holds for an appropriately expanded structure. The question then becomes: What is the appropriate expansion?
3. CASE STUDY: THE RATIONALS
The big Ramsey degrees for the rationals were determined by 1979. Laver in 1969 (unpublished, see [10]) utilized a Ramsey theorem for trees due to Milliken [50] (Theorem 3.2) to find upper bounds. Devlin completed the picture in his PhD\mathrm{PhD} thesis [10], calculating the big Ramsey degrees of the rationals. These surprisingly turn out to be related to the odd coefficients in the Taylor series of the tangent function: The big Ramsey degree for nn-element subsets of the rationals is T(n)=(2n-1)!c_(2n-1)T(n)=(2 n-1)!c_{2 n-1}, where c_(k)c_{k} is the kk th coefficient in the Taylor series for the tangent function, tan(x)=sum_(k=0)^(oo)c_(k)x^(k)\tan (x)=\sum_{k=0}^{\infty} c_{k} x^{k}. As Todorcevic states, the big Ramsey degrees for the rationals "characterize the Ramsey theoretic properties of the countable dense linear ordering (Q, < )(\mathbb{Q},<) in a very precise sense. The numbers T(n)T(n) are some sort of Ramsey degrees that measure the complexity of an arbitrary finite coloring of the nn-element subsets of Q\mathbb{Q} modulo, of course, restricting to the nn-element subsets of XX for some appropriately chosen dense linear subordering XX of Q\mathbb{Q}." (page 143, [66], notation modified)
We present Devlin's characterization of the big Ramsey degrees of the rationals and the four main steps in his proof. (A detailed proof appears in Section 6.3 of [66].) Then we will present a method from [8] using coding trees of 1-types which bypasses nonessential constructs, providing what we see as a satisfactory answer to Question 2.2 for the rationals.
We use some standard mathematical logic notation, providing definitions as needed for the general mathematician. The set of all natural numbers {0,1,2,dots}\{0,1,2, \ldots\} is denoted by omega\omega. Each natural number k in omegak \in \omega is equated with the set {0,dots,k-1}\{0, \ldots, k-1\} and its natural linear ordering. For us k in omegak \in \omega and k < omegak<\omega are synonymous. For k in omega,k^( < omega)k \in \omega, k^{<\omega} denotes the tree of all finite sequences with entries in {0,dots,k-1}\{0, \ldots, k-1\}, and omega^( < omega)\omega^{<\omega} denotes the tree of all finite sequences of natural numbers. Finite sequences with any sort of entries are thought of as functions with domain some natural number. Thus, for a finite sequence tt the length of tt, denoted |t||t|, is the domain of the function tt, and for i in dom(t),t(i)i \in \operatorname{dom}(t), t(i) denotes the ii th entry of the sequence tt. For â„“in omega\ell \in \omega, we write t↾ℓt \upharpoonright \ell to denote the initial segment of tt of length â„“\ell if â„“ <= |t|\ell \leq|t|, and tt otherwise. For two finite sequences ss and tt, we write s⊑ts \sqsubseteq t when ss is an initial segment of tt, and we write sâŠts \sqsubset t when ss is a proper initial segment of tt, meaning that s⊑ts \sqsubseteq t and s!=ts \neq t. We write s^^ts \wedge t to denote the meet of ss and tt, that is, the longest sequence which is an initial segment of both ss and tt. Given a subset SS of a tree of finite sequences, the meet
closure of SS, denoted cl(S)\operatorname{cl}(S), is the set of all nodes in SS along with the set of all meets s^^ts \wedge t, for s,t in Ss, t \in S.
A Ramsey theorem for trees, due to Milliken, played a central role in Devlin's work and has informed subsequent approaches to finding upper bounds for big Ramsey degrees. In this area, a subset T subeomega^( < omega)T \subseteq \omega^{<\omega} is called a tree if there is a subset L_(T)sube omegaL_{T} \subseteq \omega such that T=T={t↾ℓ:t in T,â„“inL_(T)}\left\{t \upharpoonright \ell: t \in T, \ell \in L_{T}\right\}. Thus, a tree is closed under initial segments of lengths in L_(T)L_{T}, but not necessarily closed under all initial segments in omega^( < omega)\omega^{<\omega}. The height of a node tt in TT, denoted ht_(T)(t)\operatorname{ht}_{T}(t), is the order-type of the set {s in T:sâŠt}\{s \in T: s \sqsubset t\}, linearly ordered by âŠ\sqsubset. We write T(n)T(n) to denote {t in T:ht_(T)(t)=n}\left\{t \in T: \operatorname{ht}_{T}(t)=n\right\}. For t in Tt \in T, let Succ_(T)(t)={s↾(|t|+1):s in T\operatorname{Succ}_{T}(t)=\{s \upharpoonright(|t|+1): s \in T and tâŠs}t \sqsubset s\}, noting that Succ_(T)(t)sube T\operatorname{Succ}_{T}(t) \subseteq T only if |t|+1inL_(T)|t|+1 \in L_{T}.
A subtree S sube TS \subseteq T is a strong subtree of TT if L_(S)subeL_(T)L_{S} \subseteq L_{T} and each node ss in SS branches as widely as TT will allow, meaning that for s in Ss \in S, for each t inSucc_(T)(s)t \in \operatorname{Succ}_{T}(s) there is an extension s^(')in Ss^{\prime} \in S such that t⊑s^(')t \sqsubseteq s^{\prime}. For the next theorem, define prod_(i < d)T_(i)(n)\prod_{i<d} T_{i}(n) to be the set of sequences (t_(0),dots,t_(d-1))\left(t_{0}, \ldots, t_{d-1}\right) where t_(i)inT_(i)(n)t_{i} \in T_{i}(n), the product of the nnth levels of the trees T_(i)T_{i}. Then let
The following is the strong tree version of the Halpern-Läuchli theorem.
Theorem 3.1 (Halpern-Läuchli, [34]). Let dd be a positive integer, T_(i)subeomega^( < omega)(i < d)T_{i} \subseteq \omega^{<\omega}(i<d) be finitely branching trees with no terminal nodes, and r >= 2r \geq 2. Given a coloring c:ox_(i < d)T_(i)rarr rc: \otimes_{i<d} T_{i} \rightarrow r, there is an increasing sequence (:m_(n):n < omega:)\left\langle m_{n}: n<\omega\right\rangle and strong subtrees S_(i) <= T_(i)S_{i} \leq T_{i} such that for all i < di<d and n < omega,S_(i)(n)subeT_(i)(m_(n))n<\omega, S_{i}(n) \subseteq T_{i}\left(m_{n}\right), and cc is constant on ox_(i < d)S_(i)\otimes_{i<d} S_{i}.
Harrington (unpublished) devised an innovative proof of the Halpern-Läuchli theorem which used Cohen forcing. The forcing helps find good nodes in the trees T_(i)T_{i} from which to start building the subtrees S_(i)S_{i}. From then on, the forcing is used omega\omega many times, each time running an unbounded search for finite sets S_(i)(n)S_{i}(n) which satisfy that level of the HalpernLäuchli theorem. Being finite, each S_(i)(n)S_{i}(n) is in the ground model. The proof entails neither passing to a generic extension nor any use of Shoenfield's Absoluteness Theorem.
A kk-strong subtree is a strong subtree with kk many levels. The following theorem is proved inductively using Theorem 3.1.
Theorem 3.2 (Milliken, [50]). Let T subeomega^( < omega)T \subseteq \omega^{<\omega} be a finitely branching tree with no terminal nodes, k >= 1k \geq 1, and r >= 2r \geq 2. Given a coloring of all kk-strong subtrees of TT into rr colors, there is an infinite strong subtree S sube TS \subseteq T such that all kk-strong subtrees of SS have the same color.
For more on the Halpern-Läuchli and Milliken theorems, see [21, 46,66]. Now we look at Devlin's proof of the exact big Ramsey degrees of the rationals, as it has bearing on many current approaches to big Ramsey degrees.
The rationals can be represented by the tree 2^( < omega)2^{<\omega} of binary sequences with the lexicographic order â—ƒ\triangleleft defined as follows: Given s,t in2^( < omega)s, t \in 2^{<\omega} with s!=ts \neq t, and letting uu denote s^^ts \wedge t, define sâ—ƒts \triangleleft t to hold if and only if (|u| < |s|(|u|<|s| and s(|u|)=0)s(|u|)=0) or (|u| < |t|(|u|<|t| and t(|u|)=1)t(|u|)=1). Then (2^( < omega),â—ƒ)\left(2^{<\omega}, \triangleleft\right) is a dense linear order. The following is Definition 6.11 in [66], using the terminology of [62]. For |s| < |t||s|<|t|, the number t(|s|)t(|s|) is called the passing number of tt at ss.
Definition 3.3. For A,B subeomega^( < omega)A, B \subseteq \omega^{<\omega}, we say that AA and BB are similar if there is a bijection f:cl(A)rarr cl(B)f: \operatorname{cl}(A) \rightarrow \operatorname{cl}(B) such that for all s,t in cl(A)s, t \in \operatorname{cl}(A),
(a) (preserves end-extension) s⊑t<=>f(s)⊑f(t)s \sqsubseteq t \Leftrightarrow f(s) \sqsubseteq f(t),
Similarity is an equivalence relation; a similarity equivalence class is called a similarity type. We now outline the four main steps to Devlin's characterization of big Ramsey degrees in the rationals. Fix n >= 1n \geq 1.
I. (Envelopes) Given a subset A sube2^( < omega)A \subseteq 2^{<\omega} of size nn, let kk be the number of levels in cl(A)\operatorname{cl}(A). An envelope of AA is a kk-strong subtree E(A)E(A) of 2^( < omega)2^{<\omega} such that A sube E(A)A \subseteq E(A). Given any kk-strong subtree SS of 2^( < omega)2^{<\omega}, there is exactly one subset B sube SB \subseteq S which is similar to AA. This makes it possible to transfer a coloring of the similarity copies of AA in 2^( < omega)2^{<\omega} to the kk-strong subtrees of 2^( < omega)2^{<\omega} in a well-defined manner.
II. (Finite Big Ramsey Degrees) Apply Milliken's theorem to obtain an infinite strong subtree T sube2^( < omega)T \subseteq 2^{<\omega} such that every similarity copy of AA in TT has the same color. As there are only finitely many similarity types of sets of size nn, finitely many applications of Milliken's theorem results in an infinite strong subtree S sube2^( < omega)S \subseteq 2^{<\omega} such that the coloring is monochromatic on each similarity type of size nn. This achieves finite big Ramsey degrees.
III. (Diagonal Antichain for Better Upper Bounds) To obtain the exact big Ramsey degrees, Devlin constructed a particular antichain of nodes D sube2^( < omega)D \subseteq 2^{<\omega} such that (D,â—ƒ)(D, \triangleleft) is a dense linear order and no two nodes in the meet closure of DD have the same length, a property called diagonal. He also required (**)(*) : All passing numbers at the level of a terminal node or a meet node in cl(D)\operatorname{cl}(D) are 0 , except of course the rightmost extension of the meet node. Diagonal antichains turn out to be essential to characterizing big Ramsey degrees, whereas the additional requirement (**)(*) is now seen to be nonessential when viewed through the lens of coding trees of 1-types.
IV. (Exact Big Ramsey Degrees) To characterize the big Ramsey degrees, Devlin proved that the similarity type of each subset of DD of size nn persists in every subset D^(')sube DD^{\prime} \subseteq D such that (D^('),â—ƒ)\left(D^{\prime}, \triangleleft\right) is a dense linear order. The similarity types of antichains in DD thus form a canonical partition for linear orders of size nn. By calculating the number of different similarity types of subsets of DD of size nn, Devlin found the big Ramsey degrees for the rationals.
FIGURE 1
Coding tree S(Q)\mathbb{S}(\mathbb{Q}) of 1-types for (Q, < )(\mathbb{Q},<) and the linear order represented by its coding nodes.
Now we present the characterization of the big Ramsey degrees for the rationals using coding trees of 1-types. Coding trees on 2^( < omega)2^{<\omega} were first developed in [13] to solve the problem of whether or not the triangle-free homogeneous graph has finite big Ramsey degrees. The presentation given here is from [8], where the notion of coding trees was honed using model-theoretic ideas. We hope that presenting this view here will set the stage for a concrete understanding of big Ramsey degree characterizations discussed in Section 5.
Fix an enumeration {q_(0),q_(1),dots}\left\{q_{0}, q_{1}, \ldots\right\} of Q\mathbb{Q}. For n < omegan<\omega, we let Q↾n\mathbb{Q} \upharpoonright n denote the substructure ({q_(i):i in n}, < )\left(\left\{q_{i}: i \in n\right\},<\right) of (Q, < )(\mathbb{Q},<), which we refer to as an initial substructure. One can think of Q↾n\mathbb{Q} \upharpoonright n as a finite approximation in a construction of the rationals. The definition of a coding tree of 1-types in [8] uses complete realizable quantifier-free 1-types over initial substructures. Here, we shall retain the terminology of [8] but (with apologies to model-theorists) will use sets of literals instead, since this will convey the important aspects of the constructions while being more accessible to a general readership. For now, we call a set of formulas s sube{(q_(i) < x):i in n}uu{(x < q_(i)):i in n}s \subseteq\left\{\left(q_{i}<x\right): i \in n\right\} \cup\left\{\left(x<q_{i}\right): i \in n\right\} a 1-type over Q↾n\mathbb{Q} \upharpoonright n if (a) for each i < ni<n exactly one of the formulas (q_(i) < x)\left(q_{i}<x\right) or (x < q_(i))\left(x<q_{i}\right) is in ss, and (b) there is some (and hence infinitely many) j >= nj \geq n such that q_(j)q_{j} satisfies ss, meaning that replacing the variable xx by the rational number q_(j)q_{j} in each formula in ss results in a true statement. In other words, ss is a 1-type if ss prescribes a legitimate way to extend Q↾n\mathbb{Q} \upharpoonright n to a linear order of size n+1n+1.
Definition 3.4 (Coding Tree of 1-Types for Q,[8]\mathbb{Q},[8] ). For a fixed enumeration {q_(0),q_(1),dots}\left\{q_{0}, q_{1}, \ldots\right\} of the rationals, the coding tree of 1-types S(Q)\mathbb{S}(\mathbb{Q}) is the set of all 1-types over initial substructures along with a function c:omega rarrS(Q)c: \omega \rightarrow \mathbb{S}(\mathbb{Q}) such that c(n)c(n) is the 1-type of q_(n)q_{n} over Q↾n\mathbb{Q} \upharpoonright n. The treeordering is simply inclusion.
Given s inS(Q)s \in \mathbb{S}(\mathbb{Q}) let |s|=j+1|s|=j+1 where jj is maximal such that one of (x < q_(j))\left(x<q_{j}\right) or (q_(j) < x)\left(q_{j}<x\right) is in ss. For each i < |s|i<|s|, we let s(i)s(i) denote the formula from among (x < q_(i))\left(x<q_{i}\right) or (q_(i) < x)\left(q_{i}<x\right) which is in ss. The coding nodes c(n)c(n), in practice usually denoted by c_(n)c_{n}, are special distinguished nodes representing the rational numbers; c_(n)c_{n} represents the rational q_(n)q_{n}, because c_(n)c_{n} is the 1-type with parameters from among {q_(i):i in n}\left\{q_{i}: i \in n\right\} that q_(n)q_{n} satisfies. Notice that this tree S(Q)\mathbb{S}(\mathbb{Q}) has at most one splitting node per level. The effect is that any antichain of coding nodes in S(Q\mathbb{S}(\mathbb{Q} ) will automatically be diagonal. (See Figure 1, reproduced from [8].)
Fix an ordering < _("lex ")<_{\text {lex }} on the literals: For i < ji<j, define (x < q_(i)) < _("lex ")(q_(i) < x) < _("lex ")\left(x<q_{i}\right)<_{\text {lex }}\left(q_{i}<x\right)<_{\text {lex }}(x < q_(j))\left(x<q_{j}\right). Extend < _("lex ")<_{\text {lex }} to S(Q)\mathbb{S}(\mathbb{Q}) by declaring for s,t inS(Q),s < _("lex ")ts, t \in \mathbb{S}(\mathbb{Q}), s<_{\text {lex }} t if and only if ss and tt are incomparable and for i=|s^^t|,s(i) < _("lex ")t(i)i=|s \wedge t|, s(i)<_{\text {lex }} t(i).
Definition 3.5. For A,BA, B sets of coding nodes in S(Q)\mathbb{S}(\mathbb{Q}), we say that AA and BB are similar if there is a bijection f:cl(A)rarr cl(B)f: \operatorname{cl}(A) \rightarrow \operatorname{cl}(B) such that for all s,t in cl(A),fs, t \in \operatorname{cl}(A), f satisfies (a)-(c) of Definition 3.3 and (d') s < _(lex)t Longleftrightarrow f(s) < _(lex)f(t)s<_{\operatorname{lex}} t \Longleftrightarrow f(s)<_{\operatorname{lex}} f(t),
When BB is similar to AA, we call BB a similarity copy of AA. Condition (d) in Definition 3.3 implies that the lexicographic order on 2^( < omega)2^{<\omega} is preserved, and, moreover, that passing numbers at meet nodes and at terminal nodes are preserved. In ( d^(')\mathrm{d}^{\prime} ) we only need to preserve lexicographic order.
Extending Harrington's method, forcing is utilized to obtain a pigeonhole principle for coding trees of 1-types in the vein of the Halpern-Läuchli Theorem 3.1, but for colorings of finite sets of coding nodes, rather than antichains. Via an inductive argument using this pigeonhole principle, we obtain the following Ramsey theorem on coding trees.
Theorem 3.6 ([8]). Let S(Q)\mathbb{S}(\mathbb{Q}) be a coding tree of 1-types for the rationals. Given a finite set A of coding nodes in S(Q)\mathbb{S}(\mathbb{Q}) and a finite coloring of all similarity copies of AA in S(Q)\mathbb{S}(\mathbb{Q}), there is a coding subtree SS of S(Q)\mathbb{S}(\mathbb{Q}) similar to S(Q)\mathbb{S}(\mathbb{Q}) such that all similarity copies of AA in SS have the same color.
Fix n >= 1n \geq 1. By applying Theorem 3.6 once for each similarity type of coding nodes of size nn, we prove finite big Ramsey degrees, accomplishing step II while bypassing step I in Devlin's proof. Upon taking any antichain DD of coding nodes in S(Q)\mathbb{S}(\mathbb{Q}) representing a dense linear order, we obtain better upper bounds which are then proved to be exact, accomplishing steps III and IV.
Big Ramsey degrees of the rationals. In [8], we show that given n >= 1n \geq 1, the big Ramsey degree T(n)T(n) for linear orders of size nn in the rationals is the number of similarity types of antichains of coding nodes in S(Q)\mathbb{S}(\mathbb{Q}).
What then is the big Ramsey degree T(n)T(n) in the rationals? It is the number of different ways to order the indexes of an increasing sequence of rationals {q_(i_(0)) < q_(i_(1)) < cdots < q_(i_(n-1))}\left\{q_{i_{0}}<q_{i_{1}}<\cdots<q_{i_{n-1}}\right\} with incomparable 1-types along with the number of ways to order the first differences of their 1-types over initial substructures of Q\mathbb{Q}. The first difference between the 1-types of the rationals q_(i)q_{i} and q_(j)q_{j} occurs at the least kk such that q_(i) < q_(k)q_{i}<q_{k} and q_(k) < q_(j)q_{k}<q_{j}, or vice versa. This means that q_(i)q_{i} and q_(j)q_{j} are in the same interval of Q↾k\mathbb{Q} \upharpoonright k but in different intervals of Q↾(k+1)\mathbb{Q} \upharpoonright(k+1). Concretely, T(n)T(n) is the number of <<-isomorphism classes of (2n-1)(2 n-1)-tuples of integers (i_(0),dots,i_(n-1),k_(0),dots,k_(n-2))\left(i_{0}, \ldots, i_{n-1}, k_{0}, \ldots, k_{n-2}\right) with the following properties: {q_(i_(0)) < q_(i_(1)) < cdots < q_(i_(n-1))}\left\{q_{i_{0}}<q_{i_{1}}<\cdots<q_{i_{n-1}}\right\} is a set of rationals in increasing order, and for each j < n-1,q_(i_(j)) < q_(k_(j)) < q_(i_(j+1))j<n-1, q_{i_{j}}<q_{k_{j}}<q_{i_{j+1}} where k_(j) < min(i_(j),i_(j+1))k_{j}<\min \left(i_{j}, i_{j+1}\right) and is the least integer satisfying this relation.
4. HISTORICAL HIGHLIGHTS, RECENT RESULTS, AND METHODS
The Rado graph is the second example of a homogeneous structure with nontrivial big Ramsey degrees which has been fully understood in terms of its partition theory. The Rado graph R\mathbf{R} is up to isomorphism the homogeneous graph on countably many vertices which is universal for all countable graphs. It was known to Erdős and other Hungarian mathematicians in the 1960s, though possibly earlier, that the Rado graph is indivisible. In their 1975 paper [30], Erdős, Hajnal, and Pósa constructed a coloring of the edges in R\mathbf{R} into two colors such that both colors persist in each subcopy of R\mathbf{R}. Pouzet and Sauer later showed in [57] that the big Ramsey degree for edge colorings in the Rado graph is exactly two. The complete characterization of the big Ramsey degrees of the Rado graph was achieved in a pair of papers by Sauer [62] and by Laflamme, Sauer, and Vuksanovic [44], both appearing in 2006, and the degrees were calculated by Larson in [45]. The two papers [62] and [44] in fact characterized exact big Ramsey degrees for all unrestricted homogeneous structures with finitely many binary relations, including the homogeneous digraph, homogeneous tournament, and random graph with finitely many edges of different colors. Milliken's theorem was used to prove existence of upper bounds, alluding to a deep connection between big Ramsey degrees and Ramsey theorems for trees. These results are discussed in Section 5.1.
A robust and streamlined approach applicable to a large class of homogeneous structures, and recovering the previously mentioned examples (except for S(2)\mathbf{S}(2) ), was developed by Coulson, Patel, and the author in [8], building on ideas in [13] and [12]. In [8], it was shown that homogeneous structures with relations of arity at most two satisfying a strengthening of SAP, called SDAP ^(+){ }^{+}, have big Ramsey structures which are characterized in a simple manner, and therefore their big Ramsey degrees are easy to compute. The proof proceeds via a Ramsey theorem for colorings of finite antichains of coding nodes on diagonal coding
trees of 1-types. This approach bypasses any need for envelopes, the theorem producing of its own accord exact upper bounds. Moreover, the Halpern-Läuchli-style theorem, which is proved via forcing arguments to achieve a ZFC result and used as the pigeonhole principle in the Ramsey theorem, immediately yields indivisibility for all homogeneous structures satisfying SDAP^(+)\mathrm{SDAP}^{+}, with relations of any arity. These results and their methods are discussed in Section 5.1.
The kk-clique-free homogeneous graphs, denoted G_(k),k >= 3\mathbf{G}_{k}, k \geq 3, were constructed by Henson in his 1971 paper [36], where he proved these graphs to be weakly indivisible. In their 1986 paper [42], Komjáth and Rödl proved that G_(3)\mathbf{G}_{3} is indivisible, answering a question of Hajnal. A few years later, El-Zahar and Sauer gave a systematic approach in [24], proving that for each k >= 3k \geq 3, the kk-clique-free homogeneous graph G_(k)\mathbf{G}_{k} is indivisible. In 1998, Sauer proved in [60] that the big Ramsey degree for edges in G_(3)\mathbf{G}_{3} is two. Further progress on big Ramsey degrees of G_(3)\mathbf{G}_{3}, however, needed a new approach. This was achieved by the author in [13], where the method of coding trees was first developed. In [12], the author extended this work, proving that G_(k)\mathbf{G}_{k} has finite big Ramsey degrees, for each k >= 3k \geq 3. In [13] and [12], the author proved a Ramsey theorem for colorings of finite antichains of coding nodes in diagonal coding trees. These diagonal coding trees were designed to achieve very good upper bounds and directly recover the indivisibility results in [42] and [24], discovering much of the essential structure involved in characterizing their exact big Ramsey degrees. (Millikenstyle theorems on nondiagonal coding trees which fully branch at each level do not directly prove indivisibility results, and produce looser upper bounds.) In particular, after a minor modification, the trees in [13] produced exact big Ramsey degrees for G_(3)\mathbf{G}_{3}, as shown in [14]. Around the same time, exact big Ramsey degrees for G_(3)\mathbf{G}_{3} were independently proved by Balko, Chodounský, HubiÄka, KoneÄný, Vena, and Zucker, instigating the collaboration of this group with the author.
Mašulović instigated the use of category theory to prove transport principles showing that finite big Ramsey degrees can be inferred from one category to another. After proving a general transport principle in [47], he applied it to prove finite big Ramsey degrees for many universal structures and also for homogenous metric spaces with finite distance sets with a certain property which he calls compact with one nontrivial block. Mašulović proved in [48] that in categories satisfying certain mild conditions, small Ramsey degrees are minima of big Ramsey degrees. In the paper [49] with Šobot (not using category theory), finite big Ramsey degrees for finite chains in countable ordinals were shown to exist if and only if the ordinal is smaller than omega^(omega)\omega^{\omega}. Dasilva Barbosa in [9] proved that categorical precompact expansions grant upper bounds for big and small Ramsey degrees. As an application, he calculated the big Ramsey degrees of the circular directed graphs S(n)\mathbf{S}(n) for all n >= 2n \geq 2, extending the work in [43] for S(2)\mathbf{S}(2).
HubiÄka recently developed a new method to handle forbidden substructures utilizing topological Ramsey spaces of parameter words due to Carlson and Simpson [7]. In [39], he applied his method to prove that the homogeneous partial order and Urysohn SS-metric spaces (where SS is a set of nonnegative reals with 0in S0 \in S satisfying the 4 -values condition) have finite big Ramsey degrees. He also showed that this method is quite broad and can be applied to yield a short proof of finite big Ramsey degrees in G_(3)\mathbf{G}_{3}. Beginning with the upper bounds in [39], the exact big Ramsey degrees of the generic partial order have been characterized in [5] by Balko, Chodounský, HubiÄka, KoneÄný, Vena, Zucker, and the author. Also utilizing techniques from [39], Balko, Chodounský, HubiÄka, KoneÄný, NeÅ¡etÅ™il, and Vena in [2] have found a condition which guarantees finite big Ramsey degrees for binary relational homogeneous structures with strong amalgamation. Examples of structures satisfying this condition include the SS-Urysohn space for finite distance sets S,LambdaS, \Lambda-ultrametric spaces for a finite distributive lattice, and metric spaces associated to metrically homogeneous graphs of a finite diameter from Cherlin's list with no Henson constraints.
For homogeneous structures with free amalgamation, a recent breakthrough of Sauer proving indivisibility in [64] culminates a long line of work in [25-28, 61]. Complementary work appeared in [8][8], where it was proved that for finitely many relations of any
arity, SDAP^(+)\mathrm{SDAP}^{+}implies indivisibility. On the other hand, big Ramsey degrees of structures with relations of arity greater than two has only recently seen progress, beginning with [3] and [4], where Balko, Chodounský, HubiÄka, KoneÄný, and Vena found upper bounds for the big Ramsey degrees of the generic 3-hypergraph. Work in this area is ongoing and promising.
5. EXACT BIG RAMSEY DEGREES
This section presents characterizations of exact big Ramsey degrees known at the time of writing. These hold for homogeneous structures with finitely many relations of arity at most two. Two general classes have been completely understood: Structures satisfying a certain strengthening of strong amalgamation called SDAP ^(+){ }^{+}(Section 5.1) and structures whose ages have free amalgamation (Section 5.2). Lying outside of these two classes, the generic partial order has been completely understood in terms of exact big Ramsey degrees and will be briefly discussed at the end of Section 5.2. These characterizations all involve the notion of a diagonal antichain, in various trees or spaces of parameter words, representing a copy of an enumerated homogeneous structure. Here, we present these notions in terms of structures, as they are independent of the representation.
Let K\mathbf{K} be an enumerated homogeneous structure with universe {v_(n):n < omega}\left\{v_{n}: n<\omega\right\}. Let A <= K\mathbf{A} \leq \mathbf{K} be a finite substructure of K\mathbf{K}, and suppose that the universe of A\mathbf{A} is {v_(i):i in I}\left\{v_{i}: i \in I\right\} for some finite set I sube omegaI \subseteq \omega. We say that A\mathbf{A} is an antichain if for each pair i < ji<j in II there is a k(i,j) < ik(i, j)<i such that the set {k(i,j):i,j in I\{k(i, j): i, j \in I and i < j}i<j\} is disjoint from II, and
An antichain A\mathbf{A} is called diagonal if {k(i,j):i < j <= m}\{k(i, j): i<j \leq m\} has cardinality mm. We call k(i,j)k(i, j) the meet level of the pair v_(i),v_(j)v_{i}, v_{j}.
The notion of diagonal antichain is central to all characterizations of big Ramsey degrees obtained so far. It seems likely that antichains will be essential to all characterizations of big Ramsey degrees. However, preliminary work shows that some homogeneous binary relational structures, such as two or more independent linear orders, will have characterizations in their trees of 1-types involving antichains which are not diagonal, but could still be characterized via products of finitely many diagonal antichains.
The indexing of the relation symbols {R_(â„“):â„“ < L}\left\{R_{\ell}: \ell<L\right\} in the language L\mathscr{L} of K\mathbf{K} induces a lexicographic ordering on trees representing relational structures. Here, we present this idea directly on the structures. For m!=nm \neq n, we declare v_(m) < _("lex ")v_(n)v_{m}<_{\text {lex }} v_{n} if and only if {v_(m),v_(n)}\left\{v_{m}, v_{n}\right\} is an antichain and, letting kk be the meet level of the pair v_(m),v_(n)v_{m}, v_{n}, and letting â„“\ell denote the least index in LL such that v_(m)v_{m} and v_(n)v_{n} disagree on their R_(â„“)R_{\ell}-relationship with v_(k)v_{k}, either R_(â„“)(v_(k),v_(n))R_{\ell}\left(v_{k}, v_{n}\right) holds while R_(â„“)(v_(k),v_(m))R_{\ell}\left(v_{k}, v_{m}\right) does not, or else R_(â„“)(v_(n),v_(k))R_{\ell}\left(v_{n}, v_{k}\right) holds while R_(â„“)(v_(m),v_(k))R_{\ell}\left(v_{m}, v_{k}\right) does not.
Two diagonal antichains A\mathbf{A} and B\mathbf{B} in an enumerated homogeneous structure K\mathbf{K} are similar if they have the same number of vertices, and the increasing bijection from the universe A={v_(m_(i)):i <= p}A=\left\{v_{m_{i}}: i \leq p\right\} of A\mathbf{A} to the universe B={v_(n_(i)):i <= p}B=\left\{v_{n_{i}}: i \leq p\right\} of B\mathbf{B} induces an isomorphism
from A\mathbf{A} to B\mathbf{B} which preserves < _("lex ")<_{\text {lex }} and induces a map on the meet levels which, for each i < j <= pi<j \leq p, sends k(m_(i),m_(j))k\left(m_{i}, m_{j}\right) to k(n_(i),n_(j))k\left(n_{i}, n_{j}\right). This implies that the map sending the coding node c_(m_(i))c_{m_{i}} to c_(n_(i))(i <= p)c_{n_{i}}(i \leq p) in the coding tree of 1-types S(K)\mathbb{S}(\mathbf{K}) (see Definition 3.4) induces a map on the meet-closures of {c_(m_(i)):i <= p}\left\{c_{m_{i}}: i \leq p\right\} and {c_(n_(i)):i <= p}\left\{c_{n_{i}}: i \leq p\right\} satisfying Definition 3.5.
Similarity is an equivalence relation, and an equivalence class is called a similarity type. We say that K\mathbf{K} has simply characterized big Ramsey degrees if for Ain Age(K)\mathbf{A} \in \operatorname{Age}(\mathbf{K}), the big Ramsey degree of A\mathbf{A} is exactly the number of similarity types of diagonal antichains representing A. In the next subsection, we will see many homogeneous structures with simply characterized big Ramsey degrees.
5.1. Exact big Ramsey degrees with a simple characterization
The decades-long investigation of the big Ramsey degrees of the Rado graph culminated in the two papers [62] and [44]. These two papers moreover characterized the big Ramsey degrees for all unrestricted binary relational homogeneous structures. Unrestricted binary relational structures are determined by a finite language L={R_(0),dots,R_(l-1)}\mathscr{L}=\left\{R_{0}, \ldots, R_{l-1}\right\} of binary relation symbols and a nonempty constraint set C\mathscr{C} of L\mathscr{L}-structures with universe {0,1}\{0,1\} with the following property: If A\mathbf{A} and B\mathbf{B} are two isomorphic L\mathscr{L}-structures with universe {0,1}\{0,1\}, then either both are in C\mathscr{C} or neither is in C\mathscr{C}. We let HC\mathbf{H} \mathcal{C} denote the homogeneous structure such that each of its substructures with universe of size two is isomorphic to one of the structures in ⨀\bigodot. Examples of unrestricted binary relational homogeneous structures include the Rado graph, the generic directed graph, the generic tournament, and random graphs with more than one edge relation.
Given a universal constraint set C\mathcal{C}, letting k=∣Ck=\mid \mathscr{C}, Sauer showed in [62] how to form a structure, call it U_(C)\mathbf{U}_{\mathscr{C}}, with nodes in the tree k^( < omega)k^{<\omega} as vertices, such that H_(C)\mathbf{H}_{\mathscr{C}} embeds into U_(C)\mathbf{U}_{\mathscr{C}}. Fix a bijection lambda:Crarr k\lambda: \mathscr{C} \rightarrow k. Given two nodes s,t ink^( < omega)s, t \in k^{<\omega} with |s| < |t||s|<|t|, declare that t(|s|)=jt(|s|)=j if and only if the induced substructure of U_(C)\mathbf{U}_{\mathcal{C}} on universe {s,t}\{s, t\} is isomorphic to the structure lambda(j)\lambda(j) in C\mathcal{C}, where the isomorphism sends ss to 0 and tt to 1 . For two nodes s,t ink^( < omega)s, t \in k^{<\omega} of the same length, declare that for ss lexicographically less than tt, the induced substructure of U_(⨀)\mathbf{U}_{\bigodot}
to 0 and tt to 1 . As a special case, a universal graph is constructed as follows: Let each node in 2^( < omega)2^{<\omega} be a vertex. Define an edge relation EE between vertices by declaring that, for s!=ts \neq t in 2^( < omega),sEt2^{<\omega}, s E t if and only if |s|!=|t||s| \neq|t| and (|s| < |t|Longrightarrow t(|s|)=1)(|s|<|t| \Longrightarrow t(|s|)=1). Then (2^( < omega),E)\left(2^{<\omega}, E\right) is universal for all countable graphs. In particular, the Rado graph embeds into the graph (2^( < omega),E)\left(2^{<\omega}, E\right), and vice versa.
In trees of the form k^( < omega)k^{<\omega}, the notion of similarity is exactly that of Definition 3.3, and steps I-IV discussed in Section 3 outline the proof of exact big Ramsey degrees contained in the pair of papers [62] and [44]. Milliken's theorem was used to prove existence of upper bounds via strong tree envelopes. For step III, Sauer constructed in [62] a diagonal antichain D subek^( < omega)D \subseteq k^{<\omega} such that the substructure of U_(C)\mathbf{U}_{\mathcal{C}} restricted to universe DD is isomorphic to He\mathbf{H} \boldsymbol{e}, achieving upper bounds shown to be exact in [44], finishing step IV. The big Ramsey degree of a finite substructure A\mathbf{A} of H_(C)\mathbf{H}_{\mathcal{C}} is exactly the number of distinct similarity types of subsets of DD whose induced substructure in U_(C)\mathbf{U}_{\mathcal{C}} is isomorphic to A\mathbf{A}.
The work in [62] and [44] greatly influenced the author's development of coding trees and their Ramsey theorems in [13] and [12] (discussed in Section 5.2). Those papers along with a suggestion of Sauer to the author during the Banff 2018 Workshop on Unifying Themes in Ramsey Theory, to try moving the forcing arguments in those papers from coding trees to structures, informed the approach taken in the paper [8], which is now discussed.
A substructure A\mathbf{A} of K\mathbf{K} with universe A={v_(n_(0)),dots,v_(n_(m))}A=\left\{v_{n_{0}}, \ldots, v_{n_{m}}\right\} is represented by the set of coding nodes {c(n_(0)),dots,c(n_(m))}\left\{c\left(n_{0}\right), \ldots, c\left(n_{m}\right)\right\} as follows: For each i <= mi \leq m, since c(n_(i))c\left(n_{i}\right) is the quantifierfree 1-type of v_(n_(i))v_{n_{i}} over K_(n_(i))\mathbf{K}_{n_{i}}, substituting v_(n_(i))v_{n_{i}} for the variable xx into each formula in c(n_(i))c\left(n_{i}\right) which has only parameters from {v_(n_(j)):j < i}\left\{v_{n_{j}}: j<i\right\} uniquely determines the relations in A\mathbf{A} on the vertices {v_(n_(j)):j <= i}\left\{v_{n_{j}}: j \leq i\right\}. In [8], we formulated the following strengthening of SAP in order to extract a general property ensuring that big Ramsey degrees have simple characterizations.
(1) Suppose BinK\mathbf{B} \in \mathcal{K} is any structure containing A^(')\mathbf{A}^{\prime} as a substructure, and let sigma\sigma and tau\tau be 1-types over B\mathbf{B} satisfying sigma↾A^(')=tp(v^(')//A^('))\sigma \upharpoonright \mathbf{A}^{\prime}=\operatorname{tp}\left(v^{\prime} / \mathbf{A}^{\prime}\right) and tau↾A^(')=tp(w^(')//A^('))\tau \upharpoonright \mathbf{A}^{\prime}=\operatorname{tp}\left(w^{\prime} / \mathbf{A}^{\prime}\right),
(2) Suppose DinK\mathbf{D} \in \mathcal{K} extends B\mathbf{B} by one vertex, say v^('')v^{\prime \prime}, such that tp(v^('')//B)=sigma\operatorname{tp}\left(v^{\prime \prime} / \mathbf{B}\right)=\sigma.
Then there is an EinK\mathbf{E} \in \mathcal{K} extending D\mathbf{D} by one vertex, say, w^('')w^{\prime \prime}, such that tp(w^('')//B)=tau\operatorname{tp}\left(w^{\prime \prime} / \mathbf{B}\right)=\tau and E↾(Auu{v^(''),w^('')})~=C\mathbf{E} \upharpoonright\left(\mathrm{A} \cup\left\{v^{\prime \prime}, w^{\prime \prime}\right\}\right) \cong \mathbf{C}.
This amalgamation property can, of course, be presented in terms of embeddings, but the form here is indicative of how it is utilized. A free amalgamation version called SFAP is obtained from SDAP by restricting to FAP classes and requiring A^(')=A\mathbf{A}^{\prime}=\mathbf{A} and C^(')=C\mathbf{C}^{\prime}=\mathbf{C}. Both of these amalgamation properties are preserved under free superposition. A diagonal subtree of S(K)\mathbb{S}(\mathbf{K}) is a subtree such that at any level, at most one node branches, the branching degree is two, and branching and coding nodes never occur on the same level. Diagonal coding trees are subtrees of S(K)\mathbb{S}(\mathbf{K}) which are diagonal and represent a subcopy of K\mathbf{K}. The property SDAP^(+)\mathrm{SDAP}^{+}holds for a homogeneous structure K\mathbf{K} if (a) its age satisfies SDAP, (b) there is a
diagonal coding subtree of S(K)\mathbb{S}(\mathbf{K}), and (c) a technicality called the Extension Property which in most cases is trivially satisfied. Classes of the form Forb(F)\operatorname{Forb}(\mathscr{F}) where F\mathscr{F} is a finite set of 3-irreducible structures, meaning each triple of vertices is in some relation, satisfy SFAP; their ordered versions satisfy SDAP^(+)\mathrm{SDAP}^{+}.
A version of the Halpern-Läuchli theorem for diagonal coding trees was proved in [8] using the method of forcing to obtain a ZFC result, with the following theorem as an immediate consequence.
Theorem 5.3 ([8]). Let K\mathbf{K} be a homogeneous structure satisfying SDAP^(+)\mathrm{SDAP}^{+}, with finitely many relations of any arity. Then K\mathbf{K} is indivisible.
For relations of arity at most two, an induction proof then yields a Ramsey theorem for finite colorings of finite antichains of coding nodes in diagonal coding trees. This accomplishes steps I-III simultaneously and directly, without any need for envelopes, providing upper bounds which are then proved to be exact, finishing step IV.
Theorem 5.4 ([8]). Let K\mathbf{K} be a homogeneous structure satisfying SADP^(+)\mathrm{SADP}^{+}, with finitely many relations of arity at most two. Then K\mathbf{K} admits a big Ramsey structure and, moreover, has simply characterized big Ramsey degrees.
5.2. Big Ramsey degrees for free amalgamation classes
An obstacle to progress in partition theory of homogeneous structures had been the fact that Milliken's theorem is not able to handle forbidden substructures, for instance, triangle-free graphs. Most results up to 2010 had either utilized Milliken's theorem or a variation (as in [43,62][43,62] ) or else used difficult direct methods (as in [60]) which did not lend naturally to generalizations. The idea of coding trees came to the author during the her stay at the Isaac Newton Institute in 2015 for the programme, Mathematical, Foundational and Computational Aspects of the Higher Infinite, culminating in the work [13]. The ideas behind coding trees included the following: Knowing that at the end of the process one will want a diagonal antichain representing a copy of G_(3)\mathbf{G}_{3}, starting with a tree where vertices in G_(3)\mathbf{G}_{3} are represented by special nodes on different levels should not hurt the results. Further, by using special nodes to code the vertices of G_(3)\mathbf{G}_{3} into the trees, one might have a chance to prove Milliken-style theorems on a collection of trees, each of which codes a subcopy of G_(3)\mathbf{G}_{3}.
The author had made a previous attempt at this problem starting early in 2012. Upon stating her interest this problem, Todorcevic (2012, at the Fields Institute Thematic Program on Forcing and Its Applications) and Sauer (2013, at the Erdős Centenary Meeting) each told the author that a new kind of Milliken theorem would need to be developed in order to handle triangle-free graphs, which intrigued her even more. Though unknown to her at the
time, a key piece to this puzzle would be Harrington's forcing proof of the Halpern-Läuchli theorem, which Laver was kind enough to outline to her in 2011. (At that time, the author was unaware of the proof in [67].) While at the INI in 2015, Bartošová reminded the author of her interest in big Ramsey degrees of G_(3)\mathbf{G}_{3}. Having had time by then to fill out and digest Laver's outline, it occurred to the author to try approaching the problem first with the strongest tool available, namely forcing.
As the results and main ideas of the methods in [12,13,71][12,13,71] have been discussed in the previous section, we now present the characterization of big Ramsey degrees in [6].
Theorem 5.5 ([6]). Let K\mathbf{K} be a homogeneous structure with finitely many relations of arity at most two such that Age(K)=Forb(F)\operatorname{Age}(\mathbf{K})=\operatorname{Forb}(\mathcal{F}) for some finite set F\mathscr{F} of finite irreducible structures. Then K\mathbf{K} admits a big Ramsey structure.
As a concrete example, we present the exact characterization for triangle-free graphs. In Figure 2, on the left is the beginning of G_(3)\mathbf{G}_{3} with some fixed enumeration of the vertices as {v_(n):n < omega}\left\{v_{n}: n<\omega\right\}. The nnth coding node in the tree S=S(G_(3))sube2^( < omega)\mathbb{S}=\mathbb{S}\left(\mathbf{G}_{3}\right) \subseteq 2^{<\omega} represents the nnth vertex v_(n)v_{n} in G_(3)\mathbf{G}_{3}, where passing number 0 represents a nonedge and passing number 1 represents an edge. Equivalently, S\mathbb{S} is the coding tree of 1-types for G_(3)\mathbf{G}_{3}, as the left branch at the level of c_(n)c_{n} represents the literal (xZv_(n))\left(x \not Z v_{n}\right) and the right branch represents (xEv_(n))\left(x E v_{n}\right)
FIGURE 2
Coding tree S(G_(3))\mathbb{S}\left(\mathbf{G}_{3}\right) and the triangle-free graph represented by its coding nodes.
Given an antichain AsubeK\mathbf{A} \subseteq \mathbf{K}, we say that A\mathbf{A} is a diagonal substructure if, letting II be the set of indices of vertices in A\mathbf{A}, the following hold: (a) For each i in I,v_(i)i \in I, v_{i} has an edge with v_(m)v_{m} for some m < im<i; let m_(i)m_{i} denote the least such mm. (b) If i < ji<j are in II with v_(i)v_(j)v_{i} \not v_{j} and m_(j) < im_{j}<i, then there is some n in in \in i such that v_(i)Ev_(n)v_{i} E v_{n} and v_(j)Ev_(n)v_{j} E v_{n}, and the least such nn, denoted n(i,j)n(i, j) is not in II. (c) For each i,j,k,â„“in Ii, j, k, \ell \in I (not necessarily distinct) with i < j,k < â„“i<j, k<\ell, (i,j)!=(k,â„“),n_(j) < i(i, j) \neq(k, \ell), n_{j}<i, and n_(â„“) < kn_{\ell}<k, we have n(i,j)!=n(k,â„“)n(i, j) \neq n(k, \ell). Given a finite triangle-free graph A\mathbf{A}, the big Ramsey degree T(A)T(\mathbf{A}) in G_(3)\mathbf{G}_{3} is the number of different diagonal substructures representing a copy of A\mathbf{A}.
We conclude this section by mentioning the exact big Ramsey degrees in the generic partial order in [5]. This result begins with the upper bounds proved by HubiÄka in [39] and then proceeds by taking a diagonal antichain DD representing the generic partial order with additional structure of interesting levels built into DD. A level â„“\ell of DD is interesting if there are exactly two nodes, say ss, tt, in that level so that (**)(*) for exactly one relation rho in{ < , > ,_|_}\rho \in\{<,>, \perp\}, given any s^('),t^(')in Ds^{\prime}, t^{\prime} \in D extending s,ts, t, respectively, s^(')rhot^(')s^{\prime} \rho t^{\prime}, while there is no such relation for the pair s↾(â„“-1),t↾(â„“-1)s \upharpoonright(\ell-1), t \upharpoonright(\ell-1). Since an interesting level for a pair of nodes s,ts, t predetermines the relations between any pair s^('),t^(')s^{\prime}, t^{\prime} extending s,ts, t, respectively, passing numbers are unnecessary to the characterization. The big Ramsey degree of a given finite partial order P\mathbf{P} is then the number of different diagonal antichains A sube DA \subseteq D representing P\mathbf{P} along with the order in which the interesting levels are interspersed between the splitting levels and the nodes in AA.
6. OPEN PROBLEMS AND RELATED DIRECTIONS
Section 2 laid out the guiding questions for big Ramsey degrees. Here we discuss some of the major open problems in big Ramsey degrees and ongoing research in cognate areas.
Problem 6.2. For results whose proofs use the method of forcing, find new proofs which are purely combinatorial.
This has been done for the triangle-free graph by HubiÄka in [39], but new methods will be needed for kk-clique-free homogeneous graphs for k >= 4k \geq 4 and other such FAP classes.
The next problem has to do with topological dynamics of automorphism groups of homogeneous structures. The work of Zucker in [70] has established a connection but not a complete correspondence yet.
Problem 6.3. Does every homogeneous structure with finite big Ramsey degrees also carry a big Ramsey structure? Is there an exact correspondence, in the vein of the KPTcorrespondence, between big Ramsey structures and topological dynamics?
Finally, we mention several areas of ongoing study related to the main focus of this paper. Computability-theoretic and reverse mathematical aspects have been investigated by Anglès d'Auriac, Cholak, Dzhafarov, Monin, and Patey. In their treatise [1], they show that the Halpern-Läuchli theorem is computably true and find reverse-mathematical strengths for various instances of the product Milliken theorem and the big Ramsey structures of the rationals and the Rado graph. As these structures both have simply characterized big Ramsey degrees, it will be interesting to see if different reverse mathematical strengths emerge for structures such as the triangle-free homogeneous graph or the generic partial order.
Extending Harrington's forcing proof to the uncountable realm, Shelah in [59] showed that it is consistent, assuming certain large cardinals, that the Halpern-Läuchli theorem holds for trees 2^( < kappa)2^{<\kappa}, where kappa\kappa is a measurable cardinal. Džamonja, Larson, and Mitchell applied a slight modification of his theorem to characterize the big Ramsey degrees for the kappa\kappa-rationals and the kappa\kappa-Rado graph in [22] and [23]. Their characterizations have as their basis the characterizations of Devlin and Laflamme-Sauer-Vuksanovic for the rationals and Rado graph, respectively, but also involve well-orderings of each level of the tree 2^( < kappa)2^{<\kappa}, necessitated by kappa\kappa being uncountable. The field of big Ramsey degrees for uncountable
homogeneous structures is still quite open, but the fleshing out of the Ramsey theorems on trees of uncountable height has seen some recent work in [19,20,68][19,20,68].
The next problem comes from a general question in [41].
Problem 6.4. Develop infinite-dimensional Ramsey theory on spaces of copies of a homogeneous structure.
For a set N sube omegaN \subseteq \omega, let [N]^(omega)[N]^{\omega} denote the set of all infinite subsets of NN, and note that [omega]^(omega)[\omega]^{\omega} represents the Baire space. The infinite-dimensional Ramsey theorem of Galvin and Prikry [33] says that given any Borel subset X\mathcal{X} of the Baire space, there is an infinite set NN such that [N]^(omega)[N]^{\omega} is either contained in X\mathcal{X} or is disjoint from X\mathcal{X}. Ellentuck's theorem in [29] found optimality in terms of sets with the property of Baire with respect to a finer topology. The question in [41] asks for extensions of these theorems to subspaces of [omega]^(omega)[\omega]^{\omega}, where each infinite set represents a copy of some fixed homogeneous structure. A GalvinPrikry-style theorem for spaces of copies of the Rado graph has been proved by the author in [17]. By a comment of Todorcevic in Luminy in 2019, the infinite-dimensional Ramsey theorem should ideally also recover exact big Ramsey degrees. Such a theorem is being written down by the author for structures satisfying SDAP^(+)\mathrm{SDAP}^{+}with relations of arity at most two. This is one instance where coding trees are necessitated to be diagonal in order for the infinite dimensional Ramsey theorem to directly recover exact big Ramsey degrees.
We close by mentioning that structural Ramsey theory has been central in investigations of ultrafilters which are relaxings of Ramsey ultrafilters in the same way that big Ramsey degrees are relaxings of Ramsey's theorem. An exposition of recent work appearing in [16] will give the reader yet another view of the power of Ramsey theory.
This work was partially supported by National Science Foundation Grant DMS-1901753.
REFERENCES
[1] P. E. Anglès d'Auriac, P. A. Cholak, D. D. Dzhafarov, B. Monin, and L. Patey, Milliken's tree theorem and its applications: a computability-theoretic perspective. Mem. Amer. Math. Soc. (to appear).
[3] M. Balko, D. Chodounský, J. HubiÄka, M. KoneÄný, and L. Vena, Big Ramsey degrees of 3-uniform hypergraphs. Acta Math. Univ. Comenian. LXXXVIII (2019), no. 3, 415-422.
[4] M. Balko, D. Chodounsky, J. HubiÄka, M. KoneÄny, and L. Vena, Lluis, Big Ramsey degrees of 3-uniform hypergraphs are finite. Combinatorica 42 (2022), no. 5, 659-672.
[6] M. Balko, D. Chodounský, N. Dobrinen, J. HubiÄka, M. KoneÄný, L. Vena, and A. Zucker, Exact big Ramsey degrees via coding trees. 2021, arXiv:2110.08409.
[7] T. Carlson and S. G. Simpson, A dual form of Ramsey's theorem. Adv. Math. 53 (1984), no. 3, 265-290.
[9] K. Dasilva Barbosa, A categorical notion of precompact expansions. 2020, arXiv:2002.11751.
[10] D. Devlin, Some partition theorems for ultrafilters on omega\omega. Ph.D. thesis, Dartmouth College, 1980 .
[11] N. Dobrinen, Forcing in Ramsey theory. RIMS Kokyuroku 2042 (2017), 17-33.
[12] N. Dobrinen, The Ramsey theory of Henson graphs. J. Math. Log. (2022). DOI 10.1142/S0219061322500180.
[13] N. Dobrinen, The Ramsey theory of the universal homogeneous triangle-free graph. J. Math. Log. 20 (2020), no. 2, 2050012,75 pp.
[14] N. Dobrinen, Ramsey theory of the universal homogeneous triangle-free graph, Part II: exact big Ramsey degrees. 2020, arXiv:2009.01985.
[15] N. Dobrinen, Ramsey Theory on infinite structures and the method of strong coding trees. In Contemporary logic and computing, edited by A. Rezus, pp. 444-467, College Publications, London, 2020.
[16] N. Dobrinen, Topological Ramsey spaces dense in forcings. In Structure and randomness in computability and set theory, edited by D. Cenzer and J. Zapletal, pp. 3-58, World Scientific, 2020.
[17] N. Dobrinen, Borel sets of Rado graphs and Ramsey's theorem. In European Journal of Combinatorics, Proc. 2016 Prague DocCourse on Ramsey Th. To appear, arXiv:1904.00266.
[18] N. Dobrinen and W. Gasarch, When Ramsey theory fails settle for more colors (Big Ramsey Degrees!). SIGACT News Open Prob. Col. 51 (2020), no. 4, 30-46.
[19] N. Dobrinen and D. Hathaway, The Halpern-Läuchli theorem at a measurable cardinal. J. Symbolic Logic 82 (2017), no. 4, 1560-1575.
[20] N. Dobrinen and D. Hathaway, Forcing and the Halpern-Läuchli theorem. J. Symbolic Logic 85 (2020), no. 1, 87-102.
[21] P. Dodos and V. Kanellopoulos, Ramsey theory for product spaces. Math. Surveys Monogr. 212, Amer. Math. Soc., Providence, 2016.
[22] M. Džamonja, J. Larson, and W. J. Mitchell, A partition theorem for a large dense linear order. Israel J. Math. 171 (2009), 237-284.
[23] M. Džamonja, J. Larson, and W. J. Mitchell, Partitions of large Rado graphs. Arch. Math. Logic 48 (2009), no. 6, 579-606.
[24] M. El-Zahar and N. Sauer, The indivisibility of the homogeneous K_(n)K_{n}-free graphs. J. Combin. Theory Ser. B 47 (1989), no. 2, 162-170.
[25] M. El-Zahar and N. Sauer, Ramsey-type properties of relational structures. Discrete Math. 94 (1991), no. 1, 1-10.
[26] M. El-Zahar and N. Sauer, On the divisibility of homogeneous directed graphs. Canad. J. Math. 45 (1993), no. 2, 284-294.
[27] M. El-Zahar and N. Sauer, On the divisibility of homogeneous hypergraphs. Combinatorica 14 (1994), no. 2, 159-165.
[28] M. El-Zahar and N. Sauer, Indivisible homogeneous directed graphs and a game for vertex partitions. Discrete Math. 291 (2005), no. 1-3, 99-113.
[29] E. Ellentuck, A new proof that analytic sets are Ramsey. J. Symbolic Logic 39 (1974), no. 1, 163-165.
[30] P. Erdős, A. Hajnal, and L. Pósa, Strong embeddings of graphs into colored graphs. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday), vol. I, pp. 585-595, Colloq. Math. Soc. János Bolyai 10, North-Holland, Amsterdam, 1975.
[36] C. W. Henson, A family of countable homogeneous graphs. Pacific J. Math. 38 (1971), no. 1, 69-83.
[37] G. Hjorth, An oscillation theorem for groups of isometries. Geom. Funct. Anal. 18 (2008), no. 2, 489-521.
[38] J. Howe, Big Ramsey degrees in homogeneous structures. Ph.D. thesis, University of Leeds, Expected, 2021.
[39] J. HubiÄka, Big Ramsey degrees using parameter spaces. 2020, arXiv:2009.00967.
[40] J. HubiÄka and J. NeÅ¡etÅ™il, All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms). Adv. Math. 356 (2019), 106791, 89 pp.
[44] C. Laflamme, N. Sauer, and V. Vuksanovic, Canonical partitions of universal structures. Combinatorica 26 (2006), no. 2, 183-205.
[45] J. Larson, Counting canonical partitions in the random graph. Combinatorica 28 (2008), no. 6, 659-678.
[46] J. Larson, Sets and extensions in the twentieth century. In Handbook of the history of logic, 6, infinite combinatorics, pp. 145-357, North-Holland, 2012.
[47] D. Mašulović, Finite big Ramsey degrees in universal structures. J. Combin. Theory Ser. A 170 (2020), no. 1, 105137, 30 pp.
[48] D. Mašulović, Ramsey degrees: big vs. small. European J. Combin. 95 (2021), 103323,25pp103323,25 \mathrm{pp}.
[49] D. Mašulović and B. Šobot, Countable ordinals and big Ramsey degrees. Combinatorica 41 (2021), no. 3, 425-446.
[50] K. R. Milliken, A Ramsey theorem for trees. J. Combin. Theory Ser. A 26 (1976), 215-237.
[51] J. Nešetřil and V. Rödl, Partitions of finite relational and set systems. J. Combin. Theory Ser. A 22 (1977), no. 3, 289-312.
[52] J. Nešetřil and V. Rödl, Ramsey classes of set systems. J. Combin. Theory Ser. A 34 (1983), no. 2, 183-201.
[56] T. Odell and T. Schlumprecht, The distortion problem. Acta Math. 173 (1994), no. 2, 259-281.
[57] M. Pouzet and N. Sauer, Edge partitions of the Rado graph. Combinatorica 16 (1996), no. 4, 505-520.
[58] F. P. Ramsey, On a problem of formal logic. Proc. Lond. Math. Soc. (2) 30 (1929), no. 4, 264-296.
[59] S. Saharon, Strong partition relations below the power set: consistency - was Sierpinski right? II. In Sets, graphs and numbers (Budapest, 1991), pp. 637-688, Colloq. Math. Soc. János Bolyai 60, North-Holland, Amsterdam, 1992.
[60] N. Sauer, Edge partitions of the countable triangle free homogenous graph. Discrete Math. 185 (1998), no. 1-3, 137-181.
[66] S. Todorcevic, Introduction to Ramsey spaces. Princeton University Press, Princeton, New Jersey, 2010.
[67] S. Todorcevic and I. Farah, Some applications of the method of forcing. Yenisei Ser. Pure Appl. Math., Yenisei, Moscow, 1995.
[68] J. Zhang, A tail cone version of the Halpern-Läuchli theorem at a large cardinal. J. Symbolic Logic 84 (2017), no. 2, 473-496.
[69] A. Zucker, Topological dynamics of automorphism groups, ultrafilter combinatorics, and the generic point problem. Trans. Amer. Math. Soc. 368 (2016), no. 9, 6715-67406715-6740.
[70] A. Zucker, Big Ramsey degrees and topological dynamics. Groups Geom. Dyn. 13 (2018), no. 1, 235-276.
[71] A. Zucker, On big Ramsey degrees for binary free amalgamation classes. Adv. Math. 408 A (2022), 108585, 25pp25 \mathrm{pp}.
NATASHA DOBRINEN
University of Denver, Department of Mathematics, 2390 S. York St., Denver, CO 80210, USA; current address: University of Notre Dame, Department of Mathematics, 255 Hurley Building, Notre Dame, IN 46556, USA, ndobrine @ nd.edu
MEASURABLE GRAPH COMBINATORICS
ANDREW S. MARKS
ABSTRACT
We survey some recent results in the theory of measurable graph combinatorics. We also discuss applications to the study of hyperfiniteness and measurable equidecompositions.
Descriptive set theory, measurable graph combinatorics, Borel graph, amenability, Borel equivalence relations, hyperfiniteness, asymptotic dimension, equidecomposition, tilings, Lovasz Local Lemma
1. INTRODUCTION
Measurable graph combinatorics focuses on finding measurable solutions to combinatorial problems on infinite graphs. This study involves ideas and techniques from combinatorics, ergodic theory, probability theory, descriptive set theory, and theoretical computer science. We survey some recent progress in this area, focusing on the study of locally finite graphs: graphs where each vertex has finitely many neighbors. We also discuss applications to the study of hyperfiniteness of Borel actions of groups, and measurable equidecompositions.
Without any constraints such as measurability conditions, combinatorial problems on locally finite graphs often simplify to studying their restriction to finite subgraphs. This is the case with the problem of graph coloring. Recall that if G=(V,E)G=(V, E) is a graph, a (proper) YY-coloring of GG is a map c:V rarr Yc: V \rightarrow Y so that for every two adjacent vertices {x,y}in E\{x, y\} \in E, the colors assigned to these two vertices are distinct, c(x)!=c(y)c(x) \neq c(y). The chromatic number chi(G)\chi(G) of GG is the smallest cardinality of a set YY so there is a YY-coloring of GG. A classical theorem of De Bruijn and ErdÅ‘Ìs states that for a locally finite graph GG, the chromatic number of GG is equal to the supremum of the chromatic number of all finite subgraphs of GG. That is, chi(G)=s u p_("finite "H sube G)chi(H)\chi(G)=\sup _{\text {finite } H \subseteq G} \chi(H). The proof of this theorem is a straightforward compactness argument using the Axiom of Choice.
In contrast, many phenomena can influence measurable chromatic numbers beyond just the constraints imposed by finite subgraphs. We illustrate this change in behavior with a simple example. Let S^(1)S^{1} be the circle, let T:S^(1)rarrS^(1)T: S^{1} \rightarrow S^{1} be an irrational rotation, and let mu\mu be Lebesgue measure on S^(1)S^{1}. Consider the graph G_(T)G_{T} with vertex set S^(1)S^{1} and where x,yx, y are adjacent if T(x)=yT(x)=y or T(y)=xT(y)=x. Every vertex in G_(T)G_{T} has degree 2 and every connected component of G_(T)G_{T} is infinite. Hence, by alternating between two colors, it is easy to see that the classical chromatic number of G_(T)G_{T} is 2 . However, there can be no Lebesgue measurable 2-coloring of G_(T)G_{T}. Suppose c:S^(1)rarr{0,1}c: S^{1} \rightarrow\{0,1\} was a Lebesgue measurable coloring of G_(T)G_{T}, and A_(0)={x:c(x)=0}A_{0}=\{x: c(x)=0\} and A_(1)={x:c(x)=1}A_{1}=\{x: c(x)=1\} were the two color sets. Then since the coloring must alternate between the two colors, we must have T(A_(0))=A_(1)T\left(A_{0}\right)=A_{1}, and since TT is measure preserving and A_(0)A_{0} and A_(1)A_{1} are disjoint and cover S^(1)S^{1}, we therefore have lambda(A_(0))=\lambda\left(A_{0}\right)=lambda(A_(1))=(1)/(2)\lambda\left(A_{1}\right)=\frac{1}{2}. However, the transformation T^(2)T^{2} is also an irrational rotation and hence T^(2)T^{2} is ergodic, meaning any set invariant under T^(2)T^{2} must be null or conull. Since T^(2)(A_(0))=A_(0)T^{2}\left(A_{0}\right)=A_{0}, A_(0)A_{0} must be null or conull. Contradiction!
In this paper we focus on the study of combinatorial problems on Borel graphs: graphs where the set VV of vertices is a standard Borel space and where the edge relation EE is Borel as a subset of V xx VV \times V. In the setting where each vertex has at most countably many neighbors, this is equivalent to saying that there are countably many Borel functions f_(0),f_(1),dots:V rarr Vf_{0}, f_{1}, \ldots: V \rightarrow V that generate GG in the sense that xEyx E y if and only if f_(i)(x)=yf_{i}(x)=y for some ii. The equivalence follows from the Lusin-Novikov theorem [28, 18.15]. An important example of a Borel graph is the following type of Schreier graph. If aa is a Borel action of a countable group Gamma\Gamma on a standard Borel space XX and SS is a symmetric set of generators for Gamma\Gamma, then let G(a,S)G(a, S) be the graph on the vertex set V=XV=X where x,y in Vx, y \in V are adjacent if there
is a gamma in S\gamma \in S such that gamma*x=y\gamma \cdot x=y. For example, the graph associated to the irrational rotation described above is a graph of this form.
For more comprehensive surveys of this area, the reader should consult the papers [30,44]. A notable recent development we will not discuss is the connections that have been found between measurable combinatorics and the study of distributed algorithms in theoretical computer science, particularly the LOCAL model. This model of computing takes place on a large graph where each vertex represents a computer which is assigned a unique identifier, and each edge is a communication link. These processors execute the same algorithm in parallel, communicating with their neighbors in rounds to construct a global solution to some combinatorial problem. Recent work [2,3,6,17[2,3,6,17 ] has established some precise connections between measurable combinatorics and LOCAL algorithms which have already led to new theorems in both areas (see, e.g., [2,4]).
2. MEASURABLE COLORINGS
If GG is a Borel graph, we define the Borel chromatic number chi_(B)(G)\chi_{B}(G) of GG to be the smallest cardinality of a standard Borel space YY so that there is a Borel measurable YY coloring of GG. We clearly have that chi(G) <= chi_(B)(G)\chi(G) \leq \chi_{B}(G) where chi(G)\chi(G) is the classical chromatic number of GG. Borel chromatic numbers were first studied in a foundational paper of Kechris, Solecki, and Todorcevic [32].
Let G=(V,E)G=(V, E) be a graph. If x in Vx \in V is a vertex, we let N(x)={y:{x,y}in E}N(x)=\{y:\{x, y\} \in E\} denote the set of neighbors of xx. The degree of xx is the cardinality of N(x)N(x). We say that a graph is Delta\Delta-regular if every vertex has degree Delta\Delta. A basic result about graph coloring is that, given any finite graph GG of finite maximum degree Delta\Delta, there is a (Delta+1)(\Delta+1)-coloring of GG. This is easy to see by coloring the vertices of GG one by one. If we have a partial coloring of GG, then any uncolored vertex xx has at most Delta\Delta neighbors so there must be a color from the set of Delta+1\Delta+1 colors we can use to extend this partial coloring to xx. The analogous fact remains true about Borel colorings:
Theorem 2.1 (Kechris, Solecki, Todorcevic [32, PROPosItion 4.6]). If G is a Borel graph of finite maximum degree Delta\Delta, then GG has a Borel (Delta+1)(\Delta+1)-coloring.
One method of proving this theorem is to adapt the greedy algorithm described above. Recall that a set of vertices is independent if it does not contain two adjacent vertices. First, we may find a countable sequence of Borel sets A_(n)A_{n} such that each A_(n)A_{n} is independent, and their union is all vertices uuu_(n)A_(n)=V(G)\bigcup_{n} A_{n}=V(G). Then we can iteratively construct a coloring of GG in countably many steps where at step nn we color all the elements of A_(n)A_{n} the least color not already used by one of its neighbors. In general, the connection between algorithms for solving combinatorial problems and measurable combinatorics is deep. Many techniques for constructing measurable colorings are based on algorithmic ideas, since algorithms for solving combinatorial problems will often yield an explicitly definable solutions to them.
The upper bound given by Theorem 2.1 is tight; a complete graph on Delta+1\Delta+1 vertices has maximum degree Delta\Delta and chromatic number Delta+1\Delta+1. Surprisingly, the upper bound of
Theorem 2.1 is also optimal even in the case of acyclic Borel graphs. Hence, for bounded degree Borel graphs, the Borel chromatic number and classical chromatic number may be very far apart since any acyclic graph has classical chromatic number at most 2 .
Theorem 2.2 (Marks [38]). For every finite Delta\Delta, there is an acyclic Borel graph of degree Delta\Delta with no Borel Delta\Delta-coloring.
The graphs used to establish Theorem 2.2 are quite natural, and arise from Schreier graphs of actions of free products of Delta\Delta many copies of Z//2Z\mathbb{Z} / 2 \mathbb{Z}. Theorem 2.2 is proved using Martin's theorem of Borel determinacy [41] which states that in any infinite two-player game of perfect information with a Borel payoff set, one of the two players has a winning strategy. The direct use of Borel determinacy to prove this theorem leads to an interesting question of reverse mathematics since Borel determinacy requires a great deal of set-theoretic power to prove: the use of uncountably many iterates of the powerset of R\mathbb{R} [19]. We currently do not know of any simpler proof of Theorem 2.2 that avoids the use of Borel determinacy or can be proved in second-order arithmetic (which suffices for most theorems of descriptive set theory).
Problem 2.3. Is Theorem 2.2 provable in the theory Z_(2)\mathbf{Z}_{2} of full second-order arithmetic?
Recently, Brandt, Chang, GrebÃk, Grunau, Rozhoň, and Vidnyánszky [6] have shown that characterizing the set of Borel graphs of maximum degree Delta >= 3\Delta \geq 3 that have no Borel (Delta+1)(\Delta+1)-coloring is as hard as possible in a precise sense: the set of such graphs is Sigma_(2)^(1)\boldsymbol{\Sigma}_{2}^{1} complete. Here Sigma_(2)^(1)\boldsymbol{\Sigma}_{2}^{1} completeness is a logical measurement of the complexity of this problem. The proof of their theorem combines the techniques of [39] with earlier work of Todorcevic and Vidnyánszky [48] proving Sigma_(2)^(1)\boldsymbol{\Sigma}_{2}^{1} completeness for the set of locally finite Borel graphs generated by a single function that have finite Borel chromatic number. In contrast to the work of [6] for Delta >= 3\Delta \geq 3, in the case Delta=2\Delta=2, a dichotomy theorem of Carroy, Miller, Schrittesser, and Vidnyánszky [8] characterizes the 2-colorable Borel graphs in a simple way as those for which there is no Borel homomorphism from a canonical non-Borel-2-colorable graph known as L_(0)\mathbb{L}_{0}.
This type of theorem-proving it is hard to characterize the set of graphs with some combinatorial property-is familiar in finite graph theory via computational complexity theory. For example, it is a well-known theorem that the set of finite graphs that are kk-colorable for k >= 3k \geq 3 is NP-complete. Indeed, there are some surprising newly found connections between computational complexity theory and complexity in measurable combinatorics. Thornton [47] has used techniques adapted from the celebrated CSP (constraint satisfaction problem) dichotomy theorem [7,51] in theoretical computer science to bootstrap the results of [6] to show many other natural combinatorial problems on locally finite Borel graphs are either Sigma_(2)^(1)\boldsymbol{\Sigma}_{2}^{1} complete or a Pi_(1)^(1)\boldsymbol{\Pi}_{1}^{1}. The CSP dichotomy theorem concerns a certain class of natural problems in NP: general constraint satisfaction problems like graph coloring with kk colors, kk-SAT, or, more generally, computing the set of finite structures XX that have a homomorphism to a given fixed finite structure DD. The CSP dichotomy states that all
such constraint satisfaction problems are either in P\mathrm{P} (like 2-coloring or 2-SAT), or they are NP-complete (like 3-coloring or 3-SAT).
The results in [6] rule out any simple theory for understanding Borel chromatic number for locally finite Borel graphs in general. In contrast, if we weaken our measurability condition to study mu\mu-measurable colorings with respect to some Borel probability measure mu\mu instead of Borel colorings, the theory of mu\mu-measurable colorings appears to have a much closer connection to finite graph theory. If mu\mu is a Borel measure on the vertex set of a Borel graph GG, let chi_(mu)(G)\chi_{\mu}(G) be the least size of a set YY so there is a mu\mu-measurable coloring of GG. So chi(G) <= chi_(mu)(G) <= chi_(B)(G)\chi(G) \leq \chi_{\mu}(G) \leq \chi_{B}(G), since every Borel function is mu\mu-measurable.
For finite graphs of maximum degree Delta\Delta, a theorem of Brooks characterizes those connected graphs which have chromatic number of Delta+1\Delta+1. They are precisely the complete graphs on Delta+1\Delta+1 vertices, and odd cycles in the case Delta=2\Delta=2. Analogously, we have the following generalization of Brooks's theorem for mu\mu-measurable colorings:
Theorem 2.4 (Conley, Marks, Tucker-Drob [13]). Suppose that GG is a Borel graph with degree bounded by a finite Delta >= 3\Delta \geq 3. Suppose further that GG contains no complete graph on Delta+1\Delta+1 vertices. If mu\mu is any Borel probability measure on V(G)V(G), then GG admits a mu\mu measurable Delta\Delta-coloring.
Several important open problems in descriptive set theory concern whether there is a difference between being able to find a Borel solution to a problem versus being able to find a mu\mu-measurable solution with respect to every Borel probability measure mu\mu (e.g., the hyperfiniteness vs measure hyperfiniteness problem [29, PROBLEM 8.29]). Theorems 2.2 and 2.4 are encouraging in this context because they point the way towards tools that may be able to resolve these types of questions.
The proof of Theorem 2.4 is based on a technique for finding one-ended spanning subforests in Borel graphs: acyclic subgraphs on the same vertex set where each connected component has exactly one end. More recently, these techniques for finding one-ended spanning subforests were applied to prove new results in the theory of cost: a real valued invariant of countable groups arising from their ergodic actions [9].
Bernshteyn has substantially strengthened Theorem 2.4 by showing for kk within a factor of sqrtDelta\sqrt{\Delta} of Delta\Delta, there is a mu\mu-measurable kk-coloring of GG if and only if there is any kk-coloring of GG.
Theorem 2.5 (Bernshteyn [2]). There is a Delta_(0)\Delta_{0} so that if GG is a Borel graph with finite maximum degree Delta >= Delta_(0)\Delta \geq \Delta_{0} and mu\mu is a Borel probability measure on V(G)V(G), then if cc satisfies c <= sqrtD-5//2c \leq \sqrt{D}-5 / 2, then GG has a (Delta-c)(\Delta-c)-coloring if and only if GG has a mu\mu-measurable (Delta-c)(\Delta-c) coloring.
The above results give cases where the mu\mu-measurable chromatic number behaves similarly to the classical chromatic number. These two quantities may still differ by a large amount, however. Let F_(n)\mathbb{F}_{n} be the free group on nn generators and let S_(n)subeF_(n)S_{n} \subseteq \mathbb{F}_{n} be a free symmetric generating set. Let a_(n)a_{n} be the action of F_(n)\mathbb{F}_{n} on the space [0,1]^(F_(n))[0,1]^{\mathbb{F}_{n}} via the Bernoulli shift: (gamma*x)(delta)=x(gamma^(-1)delta)(\gamma \cdot x)(\delta)=x\left(\gamma^{-1} \delta\right) restricted to its free part. Let G_(n)=G(a_(n),S_(n))G_{n}=G\left(a_{n}, S_{n}\right) be the Schreier graph
of this action, and let mu_(n)=lambda^(F_(n))\mu_{n}=\lambda^{\mathbb{F}_{n}} be the product of Lebesgue measure lambda\lambda on [0,1][0,1]. Since G_(n)G_{n} is acyclic, the classical chromatic number is chi(G_(n))=2\chi\left(G_{n}\right)=2. However, chi_(mu_(n))(G_(n)) >= (n)/(log 2n)\chi_{\mu_{n}}\left(G_{n}\right) \geq \frac{n}{\log 2 n} which can be shown using results about the size of independent sets in random (2n)-regular graphs and an ultraproduct argument. This argument was first suggested by [36]; see [30] for a detailed proof. Bernshteyn has recently proven an upper bound on chi_(mu_(n))(G_(n))\chi_{\mu_{n}}\left(G_{n}\right) which is within a factor of two of this lower bound [1]. However, it remains an open problem to compute the precise rate of growth of chi_(mu_(n))(G_(n))\chi_{\mu_{n}}\left(G_{n}\right).
Bernshteyn's Theorem 2.5 and the above upper bound on chi_(mu_(n))(G_(n))\chi_{\mu_{n}}\left(G_{n}\right) are based on an adaptation of the powerful Lovász Local Lemma (LLL) to the setting of measurable combinatorics. The LLL is a tool of probabilistic combinatorics which can show the existence of objects which are described by constraints that are local in the sense that each constraint is independent of all but a small number of other constraints, and each constraint has a high probability of being satisfied. Precisely, the symmetric LLLL L L states that if A_(1),dots,A_(n)A_{1}, \ldots, A_{n} are events in a probability space which each occur with probability at most pp, each event A_(i)A_{i} is independent of all but at most dd of the other events, and ep(d+1) <= 1e p(d+1) \leq 1, then there is a positive probability none of these events occur.
The LLL is a pure existence result, and since the desired object typically exists with exponentially small probability, it was a major open problem to find an algorithmic way to quickly find satisfying assignments where none of the events A_(1),dots,A_(n)A_{1}, \ldots, A_{n} happen. In particular, a naive attempt to randomly sample from the probability distribution until a solution is found would take at least exponential time. In a breakthrough result in 2009, Moser and Tardos [42] gave an efficient randomized algorithm that can quickly compute satisfying assignments for the LLL.
Adaptations of the Moser-Tardos algorithm and the LLL to the setting of measurable combinatorics began with work of Kun [33], who used a version of the Moser-Tardos algorithm to find spanning subforests to prove a strengthening of the Gaboriau-Lyons [20] theorem in ergodic theory. More recently, Csoka, Grabowski, Mathe, Pikhurko, and Tyros [14] have proved a Borel version of the symmetric LLL for Borel graphs of subexponential growth, and Bernshteyn has proved mu\mu-measurable versions for Bernoulli shifts of groups, and probability measure preserving Borel graphs [1,2][1,2]. These results, combined with the large literature in combinatorics using the LLL to construct colorings of graphs, are the main tool in the proof of Theorem 2.5 .
It is known that there cannot be a Borel version of the symmetric LLL for bounded degree Borel graphs in general [12]. Indeed, the existence of such a theorem combined with standard coloring techniques using the LLL would contradict Theorem 2.2. However, an interesting special case remains open: a Borel version of the symmetric LLL for Borel Schreier graphs generated by Borel actions of amenable groups, which are defined in the next section. Such a version of the local lemma could be a useful tool for making progress on the open problems discussed in the next section.
The theorems we have described above are a small selection of what is now known about measurable chromatic numbers. We hope they give the reader some sense of the variety of results and tools of the subject.
3. CONNECTIONS WITH HYPERFINITENESS
A major research program in modern descriptive set theory has been to understand the relative complexity of equivalence relations under Borel reducibility. Precisely, if EE and FF are equivalence relations on standard Borel spaces XX and YY, say that EE is Borel reducible to FF if there is a Borel function f:X rarr Yf: X \rightarrow Y such that for all x,y in Xx, y \in X, we have xEy Longleftrightarrow f(x)Ff(y)x E y \Longleftrightarrow f(x) F f(y). Such a function induces a definable injection from X//EX / E to Y//FY / F. If we think of EE and FF as classification problems, this means EE is simpler than FF in the sense that any invariants that can be used to classify FF can also be used to classify EE. In the study of Borel reducibility of equivalence relations, there has been success both in understanding the abstract structure of all Borel equivalence relations under Borel reducibility, and also in proving particular nonclassification results of interest to working mathematicians. For example, Hjorth's theory of turbulence [26] gives a precise dichotomy for when an equivalence relation generated by a Polish group action can be classified by invariants that are countable structures, and turbulence has been applied to prove nonclassifiability results in C^(**)C^{*} algebras [18].
A Borel equivalence relation EE is said to be countable if every EE-class is countable. The countable Borel equivalence relations are an important and well-studied subclass of Borel equivalence relations with rich connections with operator algebras and ergodic theory. One reason for this is the Feldman-Moore theorem [31, THEOREM 1.3], which states that every countable Borel equivalence relation is induced by a Borel action of a countable group. Results proved about the dynamics of measure preserving actions of countable groups have played a played an important role in our understanding of the theory of countable Borel equivalence relations.
Understanding how the descriptive-set-theoretic complexity of countable Borel equivalence relations is related to the dynamics of the group actions that generate them is a deep problem. An important simplicity notion for Borel reducibility is hyperfiniteness: a Borel equivalence relation is hyperfinite if it can be written as an increasing union of Borel equivalence relations whose classes are all finite. The hyperfinite equivalence relations are the simplest nontrivial class of Borel equivalence relations as made precise by the Glimm-Effros dichotomy of Harrington, Kechris, and Louveau [25]. Weiss has asked if the group-theoretic notion of amenability precisely corresponds to hyperfiniteness:
Problem 3.1 (Weiss, [50]). Suppose EE is a Borel equivalence relation generated by a Borel action of a countable amenable group. Is EE hyperfinite?
Amenability was defined by von Neumann in reaction to the Banach-Tarski paradox. It is a group-theoretic notion of dynamical tameness. Precisely, a group Gamma\Gamma is amenable if and only if for every epsi > 0\varepsilon>0 and every finite S sube GammaS \subseteq \Gamma there exists some nonempty finite F sube GammaF \subseteq \Gamma such that |SF/_\F|//|F| < epsi|S F \triangle F| /|F|<\varepsilon. Such an FF is called an (epsi,S)(\varepsilon, S)-Følner set. Examples of amenable groups include finite, abelian, and solvable groups, while the free group on two generators is nonamenable. If Weiss's question has a positive answer, then amenability precisely characterizes hyperfiniteness since every nonamenable group has a nonhyperfinite Borel action.
Evidence that Weiss's question has a positive answer is given by a theorem in ergodic theory of Ornstein and Weiss [43] that every measure preserving action of an amenable group on a standard probability space is hyperfinite modulo a nullset.
Progress on Weiss's question has grown out of progress on the problem of finding Borel tilings of group actions by Følner sets. Precisely, if a:Gamma↷Xa: \Gamma \curvearrowright X is an action of a finitely generated group Gamma\Gamma, and F_(1),dots,F_(n)sube GammaF_{1}, \ldots, F_{n} \subseteq \Gamma are finite subsets of Gamma\Gamma, a tiling of aa by the shapes F_(1),dots,F_(n)F_{1}, \ldots, F_{n} is a collection of subsets A_(1),dots,A_(n)sube XA_{1}, \ldots, A_{n} \subseteq X so that the sets F_(1)*A_(1),dots,F_(n)*A_(n)F_{1} \cdot A_{1}, \ldots, F_{n} \cdot A_{n} are pairwise disjoint and form a partition of XX. Finding tilings of a group action can be thought of as a generalized coloring problem or constraint satisfaction problem of the type often studied in measurable combinatorics, and can be approached using many of the same tools. For example, Jackson, Kechris, and Louveau [27] have shown that Weiss's question has a positive answer for groups of polynomial volume growth. Their argument uses Voronoi regions around Borel maximal independent sets to make Borel tilings with desirable properties. Gao and Jackson [21] have shown that Weiss's question has a positive answer for abelian groups. Their argument centers around a more refined inductive argument to find tilings of Z^(n)\mathbb{Z}^{n} by hyperrectangles. These tilings are found by iteratively adjusting the location of the boundaries of hyperrectangular tiles that cover the space until their parallel boundaries are far apart. Schneider and Seward have extended Gao and Jackson's machinery to all locally nilpotent groups [45]. All these tilings are the building blocks out of which witnesses to hyperfiniteness are constructed.
A positive answer to the following open problem would be progress towards a positive solution to Weiss's question:
Problem 3.2. Let Gamma\Gamma be an amenable group with finite symmetric generating set SS and a:Gamma↷Xa: \Gamma \curvearrowright X be a free Borel action of aa on a standard Borel space XX. For every epsi > 0\varepsilon>0, do there exist (epsi,S)(\varepsilon, S)-Følner sets F_(1),dots,F_(n)sube GammaF_{1}, \ldots, F_{n} \subseteq \Gamma such that the action aa has a Borel tiling with shapes F_(1),dots,F_(n)F_{1}, \ldots, F_{n} ?
The existence of such tilings without any measurability conditions was only recently established by Downarowicz, Huczek, and Zhang [15]. A key step in their proof is to use Hall's matching theorem to match untiled points in a Ornstein-Weiss style quasitiling [43] to construct an exact tiling. Recall that if G=(V,E)G=(V, E) is a graph, a perfect matching of GG is a subset M sube EM \subseteq E of edges so that each vertex x in Vx \in V is incident to exactly one edge in MM. Hall's matching theorem states that a bipartite graph with bipartition A,B sube VA, B \subseteq V has a perfect matching if and only if for every finite set F sube AF \subseteq A or F sube BF \subseteq B,
|N(F)| >= |F||N(F)| \geq|F|
Recently, Problem 3.2 has been shown to have a positive answer modulo a nullset [10]. A key part of the proof is a measurable matching result proved using an idea of Lyons and Nazarov [36] that was originally used to find factor of i.i.d. perfect matchings of regular trees. Lyons and Nazarov's argument uses the Hungarian matching algorithm (repeatedly flipping augmenting paths) to show that if a bipartite Borel graph GG satisfies a certain measure-
theoretic expansion condition strengthening Hall's condition, then it has a measurable perfect matching.
Conley, Jackson, Marks, Seward, and Tucker-Drob have proven the following:
Theorem 3.3 (Conley, Jackson, Marks, Seward, Tucker-Drob [11]). Let Gamma\Gamma be a countable group admitting a normal series where each quotient of consecutive terms is a finite group or a torsion-free abelian group with finite Q\mathbb{Q}-rank, except that the top quotient can be any group of uniform local polynomial volume-growth or the lamplighter group Z_(2)-<Z\mathbb{Z}_{2} \prec \mathbb{Z}. Then every free Borel action of Gamma\Gamma is hyperfinite.
By combining this with prior work of Seward and Schneider [45, coR. 8.2] they obtain the following corollary:
Corollary 3.4. Weiss's question has a positive answer for polycyclic groups.
This is the best partial result on Weiss's question that is currently known. Significantly, Corollary 3.4 applies to groups of exponential volume growth such as certain semidirect products of Z^(n)\mathbb{Z}^{n}. All the previous work on Weiss's question applied only to groups locally of polynomial volume growth, and this seemed an inherent limitation to previous methods.
The central idea of [11] is to adapt the machinery of Gromov's theory of asymptotic dimension of groups to the setting of descriptive set theory, making a theory of Borel asymptotic dimension. These ideas were implicitly hidden in all previous work on Weiss's question, but were first made explicit in [11]. Asymptotic dimension was introduced by Gromov as a quasiisometry invariant of metric spaces, used to study geometric group theory. The asymptotic dimension of a metric space (X,rho)(X, \rho) is the least dd such that for every r > 0r>0 there is a uniformly bounded cover UU of XX so that every closed rr-ball intersects at most d+1d+1 sets in UU. Essentially, asymptotic dimension is a "large-scale" analogue of Lebesgue covering dimension. There are actually several different ways to define asymptotic dimension whose equivalences are nontrivial to prove. Proving that these different definitions still define the same notion in the Borel context is one of the keys to the work in [11]. Alternate definitions allow the conversion between Voronoi cell-type tilings patterned on the work of Jackson, Kechris, and Louveau, and covers with far apart facial boundaries pioneered by Gao and Jackson.
Resolving Weiss's question for all amenable groups appears to be a difficult problem. In general, we have a poor understanding of the geometry and structure of Følner sets in arbitrary amenable groups. Problem 3.1 for arbitrary amenable groups seems to either require significant advances in our geometric understanding of amenable groups, or completely different descriptive-set theoretic tools for attacking the hyperfiniteness problem. One question which gets at the heart of this difficulty is the following:
Problem 3.5. Suppose GG is a bounded degree Borel graph having uniformly bounded polynomial growth. Is the connectedness relation of GG hyperfinite?
The obstacle in resolving Problem 3.5 is that while polynomial growth groups have tight both upper and lower bound on their growth, Problem 3.5 only posits an upper bound on the growth of GG, which may consequently have much less uniformity in its growth than the Schreier graph associated to an action of a polynomial growth group. This lack of a lower bound on growth means that the techniques of Jackson, Kechris, and Louveau for proving hyperfiniteness of groups of polynomial growth cannot resolve Problem 3.5 Finding techniques for resolving Problem 3.5 where there is far less regular geometric structure would be one way of making progress towards resolving Weiss's question in general since we know little about any regular geometric structure in arbitrary amenable groups.
4. MEASURABLE EQUIDECOMPOSITIONS
If a:Gamma↷Xa: \Gamma \curvearrowright X is an action of a group Gamma\Gamma on a space XX, then we say sets A,B sube XA, B \subseteq X are a-equidecomposable if there are a finite partition {A_(0),dots,A_(n)}\left\{A_{0}, \ldots, A_{n}\right\} of AA and group elements gamma_(0),dots,gamma_(n)in Gamma\gamma_{0}, \ldots, \gamma_{n} \in \Gamma so that gamma_(0)A_(0),dots,gamma_(n)A_(n)\gamma_{0} A_{0}, \ldots, \gamma_{n} A_{n} is a partition of BB. For example, in this language, the Banach-Tarski paradox says that one unit ball is equidecomposable with two unit balls under the group action of isometries of R^(3)\mathbb{R}^{3}. In the last few years several new results proved about these types of geometrical paradoxes with the unifying theme that the "paradoxical" sets in many classical geometrical paradoxes can surprisingly be much nicer than one would naively expect.
It is an open problem whether Theorem 4.1 can be strengthened to yield a Borel equidecomposition, assuming AA and BB are Borel.
Key to Theorem 4.1 and other advances in measurable equidecompositions has been progress made on measurable matching problems. The connection comes from the following graph-theoretic reformulation of equidecompositions as perfect matchings. Let a:Gamma↷Xa: \Gamma \curvearrowright X be a Borel action of a group Gamma\Gamma on a space XX, let A,B,sube XA, B, \subseteq X be subsets of XX, and let S sube GammaS \subseteq \Gamma be finite. Let G(A,B,S)G(A, B, S) be the graph whose set of vertices is the disjoint union A⊔BA \sqcup B and where x in Ax \in A and Y in BY \in B are adjacent if there is a gamma in S\gamma \in S so that gamma*x=y\gamma \cdot x=y. Then it is easy to see that A,BA, B are equidecomposable using group elements from SS if and only if there is a perfect matching of the graph G(A,B,S)G(A, B, S).
Theorem 4.1 and other new results about measurable equidecompositions rely on combining process made on measurable matching problems with modern results about the
dynamics of the group actions being studied. For example, Theorem 4.1 uses the local spectral gap of Boutonnet, Ioana, and Salehi Golsefidy [5] for certain lattices in the group SO_(3)(R)\mathrm{SO}_{3}(\mathbb{R}) of rotations in R^(3)\mathbb{R}^{3}. This result is used to check that the graph G(A,B,S)G(A, B, S) satisfies the expansion condition of Lyons and Nazarov [36] which ensures the existence of a measurable matching.
Some other recent theorems about measurable equidecompositions concern Tarski's famous circle squaring problem from 1925: the question of whether a disk and square of the same area in R^(2)\mathbb{R}^{2} are equidecomposable by isometries. Tarski's circle squaring problem arose from the fact that the analogue of the Banach-Tarski paradox is false in R^(2)\mathbb{R}^{2}. This is because there are so-called Banach measures in R^(2)\mathbb{R}^{2} : finitely additive isometry-invariant measures that extend Lebesgue measure. Their existence is proved using the amenability of the isometry group of R^(2)\mathbb{R}^{2}. Hence, if Lebesgue measurable sets A,B subeR^(2)A, B \subseteq \mathbb{R}^{2} are equidecomposable, they must have the same Lebesgue measure. The real thrust of Tarski's circle squaring problem is the converse of this: the general problem of to what extent there is an equivalence between equidecomposability and having the same measure.
In 1990, Laczkovich [34] (see also [35]) gave a positive answer to Tarski's circle squaring problem using the Axiom of Choice. His proof involved sophisticated tools from Diophantine approximation and discrepancy theory to prove strong quantitative bounds on the ergodic theorem for translation actions of the torus, as well as the graph-theoretic approach to equidecomposition described above.
Theorem 4.2 (Marks, Unger [40]). Tarski's circle squaring problem has a positive solution using Borel pieces. More generally, for all n >= 1n \geq 1, if A,B subeR^(n)A, B \subseteq \mathbb{R}^{n} are bounded Borel sets with the same positive Lebesgue measure whose boundaries have upper Minkowski dimension less than n, then A and B are equidecomposable using Borel pieces.
Hence, for Borel sets whose boundaries are not wildly fractal, having the same measure is actually equivalent to having an explicitly definable Borel equidecomposition.
Theorem 4.2 uses new techniques for constructing Borel perfect matchings in Borel graphs based on first finding a real-valued Borel flow as an intermediate step. Precisely, if f:V rarrRf: V \rightarrow \mathbb{R} is a function on the vertices of a graph GG, then an ff-flow on GG is a real-valued function phi\phi on the edges of GG such that phi(x,y)=-phi(y,x)\phi(x, y)=-\phi(y, x) for every directed edge (x,y)(x, y) of GG, and such that for every x in Vx \in V the flow phi\phi satisfies Kirchoff's law,
f(x)=sum_(y in N(x))phi(x,y)f(x)=\sum_{y \in N(x)} \phi(x, y)
Given a circle and square A,B sube[0,1)^(2)A, B \subseteq[0,1)^{2} of the same area, the first step in the proof of Theorem 4.2 is finding an explicit (1_(A)-1_(B))\left(1_{A}-1_{B}\right)-flow of an appropriate Borel graph whose vertices are all the elements of [0,1)^(2)[0,1)^{2} and whose edges are generated by finitely many translations.
The advantage of working with the generality of flows is twofold. First, a flow can be constructed in countably many steps, making the error in Kirchoff's law above continuously approach 0 whereas the error in a partial matching that makes it imperfect is discrete. Second, the average of ff-flows is an ff-flow and so it is possible to integrate families of definable flows to get another definable flow. Finally, there are well known combinatorial equivalences between flows and matchings which are used in the last step of the proof of Theorem 4.2 to "round" a real-valued flow into an integer valued flow and then use it to construct a matching.
Another key ingredient in the proof of Theorem 4.2 is the hyperfiniteness of Borel actions of abelian groups. In particular, the proof of Theorem 4.2 uses a recent refinement due to Gao, Jackson, Krohne, and Seward [22] of Gao and Jackson's [21] theorem that Borel actions of abelian groups are hyperfinite. These witnesses to hyperfiniteness are used to ensure that the Ford-Fulkerson algorithm converges when it is used to round the Borel realvalued flow described above into a Borel integer-valued flow.
This flow approach to equidecomposition problems may be useful for attacking other open questions such as the Borel-Ruziewicz problem:
Problem 4.3 (Wagon [49]). Suppose n >= 2n \geq 2. Is Lebesgue measure the unique finitely additive rotation invariant probability measure defined on the Borel subsets of the nn-sphere S^(n)S^{n} ?
This question is inspired by a theorem of Margulis [37] and Sullivan [46] ( n >= 4)n \geq 4), and Drinfeld [16] (n=2,3)(n=2,3), who proved that Lebesgue measure is the unique finitely additive rotation invariant measure on the Lebesgue measurable subsets of S^(n)S^{n}. Wagon's proposed strengthening would be a more natural result since the Borel sets are the canonical sigma\sigma-algebra to measure.
ACKNOWLEDGMENTS
The author would like to thank Alekos Kechris for helpful discussions.
FUNDING
This author is partially supported by NSF grant DMS-2054182.
REFERENCES
[1] A. Bernshteyn, Measurable versions of the Lovász Local Lemma and measurable graph colorings. Adv. Math. 353 (2019), 153-223.
[2] A. Bernshteyn, Distributed algorithms, the Lovász local lemma, and descriptive combinatorics. 2020, arXiv:2004.04905.
[3] A. Bernshteyn, Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms. 2021, arXiv:2102.08797.
[4] A. Bernshteyn, A fast distributed algorithm for (Delta+1)(\Delta+1)-edge-coloring. J. Combin. Theory Ser. BB (2022).
[5] R. Boutonnet, A. Ioana, and A. Salehi Golsefidy, Local spectral gap in simple Lie groups and applications. Invent. Math. 208 (2017), no. 3, 715-802.
[6] S. Brandt, Y. Chang, J. GrebÃk, C. Grunau, V. Rozhoň, and Z. Vidnyánszky, On homomorphism graphs. 2021, arXiv:2111.03683.
[7] A. Bulatov, A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 319-330, IEEE, 2017.
[8] R. Carroy, B. Miller, D. Schrittesser, and Z. Vidnyánszky, Minimal definable graphs of definable chromatic number at least three. Forum Math. Sigma E7 (2021), no. 9, 1-16.
[9] C. T. Conley, D. Gaboriau, A. S. Marks, and R. D. Tucker-Drob, One-ended spanning subforests and treeability of groups. 2021, arXiv:2104.07431.
[10] C. T. Conley, S. Jackson, D. Kerr, A. S. Marks, B. Seward, and R. D. TuckerDrob, Følner tilings for actions of amenable groups. Math. Ann. 371 (2018), 663-683.
[11] C. T. Conley, S. Jackson, A. S. Marks, B. Seward, and R. D. Tucker-Drob, Borel asymptotic dimension and hyperfinite equivalence relations. 2000, arXiv:2009.06721.
[12] C. T. Conley, S. Jackson, A. S. Marks, B. Seward, and R. D. Tucker-Drob, Hyperfiniteness and Borel combinatorics. J. Eur. Math. Soc. (JEMS) 22 (2020), no. 3, 877-892.
[13] C. T. Conley, A. S. Marks, and R. D. Tucker-Drob, Brooks's theorem for measurable colorings. Forum Math. Sigma 4 (2016).
[15] T. Downarowicz, D. Huczek, and G. Zhang, Tilings of amenable groups. J. Reine Angew. Math. 747 (2009).
[16] V. G. Drinfeld, Finitely-additive measures on S^(2)S^{2} and S^(3)S^{3}, invariant with respect to rotations. Funktsional. Anal. i Prilozhen. 18 (1984), no. 3, 77.
[17] G. Elek, Qualitative graph limit theory, Cantor dynamical systems and constanttime distributed algorithms. 2018, arXiv:1812.07511.
[18] I. Farah, Logic and operator algebras. In Proceedings of the Seoul ICM, vol. II, edited by Sun Young Jang et al., pp. 15-39, Kyung Moon SA, 2004.
[19] H. Friedman, Higher set theory and mathematical practice. Ann. Math. Logic 2 (1971), no. 3, 245-266.
[20] D. Gaboriau and R. Lyons, A measurable-group-theoretic solution to von Neumann's problem. Invent. Math. 177 (2009), 533-540.
[21] S. Gao and S. Jackson, Countable abelian group actions and hyperfinite equivalence relations. Invent. Math. 201 (2015), no. 1, 309-383.
[22] S. Gao, S. Jackson, E. Krohne, and B. Seward, Forcing constructions and countable Borel equivalence relations. 2015, arXiv:1503.07822.
[25] L. Harrington, A. S. Kechris, and A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations. J. Amer. Math. Soc. 3 (1990), no. 4, 903-928.
[26] G. Hjorth, Classification and orbit equivalence relations. Math. Surveys Monogr. 75, American Math Society, 2000.
[27] S. Jackson, A. S. Kechris, and A. Louveau, Countable Borel equivalence relations. J. Math. Log. 2 (2002), 1-80.
[28] A. S. Kechris, Classical descriptive set theory. Grad. Texts in Math. 156, Springer, New York, 1995.
[29] A. S. Kechris, The theory of countable Borel equivalence relations. 2021. URL http://math.caltech.edu/ kechris/papers/lectures%20on%20CBER08book.pdf, preprint.
[30] A. S. Kechris and A. S. Marks, Descriptive graph combinatorics. 2020. URL http://www.math.caltech.edu/ kechris, preprint.
[31] A. S. Kechris and B. D. Miller, Topics in orbit equivalence. Lecture Notes in Math. 1852, Springer, Berlin, 2004.
[32] A. S. Kechris, S. Solecki, and S. Todorcevic, Borel chromatic numbers. Adv. Math. 141 (1999), 1-44.
[33] G. Kun, Expanders have a spanning Lipschitz subgraph with large girth. 2013, arXiv:1303.4982.
[34] M. Laczkovich, Equidecomposability and discrepancy; a solution of Tarski's circle-squaring problem. J. Reine Angew. Math. 404 (1990), 77-117.
[35] M. Laczkovich, Decomposition of sets with small boundary. J. Lond. Math. Soc. 46 (1992), 58-64.
[36] R. Lyons and F. Nazarov, Perfect matchings as IID factors of non-amenable groups. European J. Combin. 32 (2011), 1115-1125.
[37] G. A. Margulis, Some remarks on invariant means. Montash. Math. 90 (1980), no. 3, 233-235.
[38] A. S. Marks, A determinacy approach to Borel combinatorics. J. Amer. Math. Soc. 29 (2016), 579-600.
[39] A. S. Marks, Uniformity, universality, and computability theory. J. Math. Log. 17 (2017), no. 1 .
[40] A. Marks and S. Unger, Borel circle squaring. Ann. of Math. (2) 186 (2017), 581-605581-605.
[41] D. A. Martin, Borel determinacy. Ann. of Math. (2) 102 (1975), 363-371.
[42] R. Moser and G. Tardos, A constructive proof of the general Lovász Local Lemma. J. ACM 57 (2010), no. 2.
[43] D. Ornstein and B. Weiss, Ergodic theory and amenable group actions, I: the Rohlin lemma. Bull. Amer. Math. Soc. 2 (1980), 161-164.
[44] O. Pikhurko, Borel combinatorics of locally finite graphs. In Surveys in combinatorics 2021, edited by K. K. Dabrowski et al., the invited volume of the 28th British Combinatorial Conference, pp. 267-319, London Math. Soc. Lecture Note Ser., Cambridge University Press, 2021.
[45] S. Schneider and B. Seward, Locally nilpotent groups and hyperfinite equivalence relations. 2013, arXiv:1308.5853.
[46] D. Sullivan, For n > 3n>3 there is only one finitely additive rotationally invariant measure on the nn-sphere defined on all Lebesgue measurable subsets. Bull. Amer. Math. Soc. 4 (1981), no. 1, 121-123.
[47] R. Thornton, The CSP dichotomy and Borel combinatorics. 2021, preprint.
[48] S. Todorcevic and Z. Vidnyanszky, A complexity problem for Borel graphs. Invent. Math. 226 (2021), 225-249.
[49] S. Wagon, The Banach Tarski paradox. University Press, Cambridge, 1986.
[50] B. Weiss, Measurable dynamics. Contemp. Math. 26 (1984), 395-421.
[51] D. Zhuk, A proof of the CSP dichotomy conjecture. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 331-342, IEEE, 2017.
ANDREW S. MARKS
UCLA Mathematics, BOX 951555, Los Angeles, CA 90095-1555, USA, marks@math.ucla.edu
THE PARIS-HARRINGTON PRINCIPLE AND SECOND-ORDER ARITHMETIC-BRIDGING THE FINITE AND INFINITE RAMSEY THEOREM
KEITA YOKOYAMA
ABSTRACT
The Paris-Harrington principle (PH)(\mathrm{PH}) is known as one of the earliest examples of "mathematical" statements independent from the standard axiomatization of natural numbers called Peano Arithmetic (PA). In this article, we discuss various variations of PH\mathrm{PH} and examine the relations between finite and infinite Ramsey's theorem and systems of arithmetic.
MATHEMATICS SUBJECT CLASSIFICATION 2020
Primary 03F30; Secondary 03F35, 03B30, 05D10
KEYWORDS
Paris-Harrington principle, Ramsey's theorem, reverse mathematics, proof theory
1. INTRODUCTION
To prove a statement about natural numbers, we usually rely explicitly or implicitly on reasoning by mathematical induction. In the setting of mathematical logic, the axiomatic system for natural numbers consists of the axioms for discrete ordered semirings and the scheme of mathematical induction, which is known as Peano Arithmetic (PA). Within PA, one can prove many theorems in number theory or finite combinatorics, such as the existence of infinitely many prime numbers or the following finite Ramsey theorem (FRT):
(FRT) For any n,k,m,a inNn, k, m, a \in \mathbb{N}, there exists b inNb \in \mathbb{N} such that for any f:[[a,b)_(N)]^(n)rarr kf:\left[[a, b)_{\mathbb{N}}\right]^{n} \rightarrow k there exist H sube[a,b)_(N)H \subseteq[a, b)_{\mathbb{N}} and c < kc<k such that [H]^(n)subef^(-1)(c)[H]^{n} \subseteq f^{-1}(c) and |H|=m|H|=m.
(Here, [a,b)_(N)={x inN:a <= x < b}[a, b)_{\mathbb{N}}=\{x \in \mathbb{N}: a \leq x<b\} and [X]^(n)={F sube X:|F|=n}[X]^{n}=\{F \subseteq X:|F|=n\} where |F||F| denotes the cardinality of FF. We write kk for the set [0,k)_(N)[0, k)_{\mathbb{N}}.) Thus, the question might arise: can we prove all true numerical statements within PAP A ?
The answer is known to be negative. The famous incompleteness theorem by Kurt Gödel says that there is a numerical statement which is independent from PA (i.e., cannot be proved or disproved from PA). Such an independent statement is provided by diagonalization or self-reference as the liar paradox, and in particular, the numerical statement which intends to say "PA is consistent" is independent from PA. This leads to another question whether there is a "mathematical" statement which is independent from PA. The Paris-Harrington principle (PH)(\mathrm{PH}) [33] is one of the earliest and most important such examples. It is a variant of the finite Ramsey theorem which states the following:
(PH) For any n,k,a inNn, k, a \in \mathbb{N}, there exists b inNb \in \mathbb{N} such that for any f:[[a,b)_(N)]^(n)rarr kf:\left[[a, b)_{\mathbb{N}}\right]^{n} \rightarrow k there exist H sube[a,b)_(N)H \subseteq[a, b)_{\mathbb{N}} and c < kc<k such that [H]^(n)subef^(-1)(c)[H]^{n} \subseteq f^{-1}(c) and |H| > min H|H|>\min H.
Here, a set HH is said to be relatively large if |H| > min H|H|>\min H, so PH\mathrm{PH} says "for any a inNa \in \mathbb{N}, there exists a large enough finite set XX above aa such that any coloring on XX for the Ramsey theorem has a solution which is relatively large." By some standard coding of finite sets of natural numbers as single natural numbers (e.g., by binary expansion), PH\mathrm{PH} can be considered as a purely numerical statement. By easy combinatorics, one can prove PH\mathrm{PH} from the infinite Ramsey theorem (RT), thus PH\mathrm{PH} is a true statement about natural numbers.
So how can we know that PH is not provable from PA? The reason is again provided by the Gödel incompleteness, namely, PA + PH implies the consistency of PA and thus it is not provable from PA. Indeed, Paris and Harrington showed that PH\mathrm{PH} is equivalent over PA\mathrm{PA} to the correctness of PA with respect to AA EE\forall \exists-sentences (the statement "any AA EE\forall \exists-sentence provable from PA is true"), which is a strengthening of the consistency of PA.
On the other hand, many variants of the infinite Ramsey theorem are widely studied in the setting of second-order arithmetic. This is one of the central topics in the project named reverse mathematics whose ultimate goal is to determine the logical strength of mathematical theorems in various fields and classify them from viewpoints of several fields in logic. Typically, the strength of variants of the infinite Ramsey theorem is precisely calibrated from the viewpoints of computability and proof theory. Particularly, precise analyses for variants of
the Paris-Harrington principle are important approaches to identify the consistency strength of variants of the infinite Ramsey theorem.
In this article, we will overview the relations between the Paris-Harrington principle, the infinite Ramsey theorem and correctness statements (also known as reflection principles) mainly in the setting of second-order arithmetic. For this purpose, we will work with nonstandard models of arithmetic and relate the finite and infinite Ramsey theorem in them. A brief idea here is that if a nonstandard model satisfies some variant of finite Ramsey theorem with a solution of nonstandard size, then it should include a model for infinite Ramsey theorem. This can be realized by the theory of indicators introduced by Kirby and Paris [23]. We reformulate their argument and connect variants of PH\mathrm{PH} with the correctness of the infinite Ramsey theorem.
The structure of this article is the following. In Section 2, we set up basic definitions and review the studies on the Ramsey theorem in arithmetic. We give several formulations of the Paris-Harrington principle and their equivalents within second-order arithmetic in Sections 3 and 4. In Section 5, we see how the Paris-Harrington principle is related to the infinite Ramsey theorem by means of indicators. Some proofs in Section 5 require basic knowledge of nonstandard models of arithmetic.
2. FIRST- AND SECOND-ORDER ARITHMETIC AND THE RAMSEY THEOREM
In this section, we introduce fragments of first- and second-order arithmetic and set up basic definitions. For precise definitions, basic properties and other information, see, e.g., [16,21] for first-order arithmetic and [17,39] for second-order arithmetic.
We write L_(1)\mathscr{L}_{1} for the language of first-order arithmetic, which consists of constants 0,1 , function symbols,+xx+ \times, and binary relation symbols =, <==, \leq, and write L_(2)\mathscr{L}_{2} for the language of second-order arithmetic which consists of L_(1)\mathscr{L}_{1} plus another binary relation in\in. We use x,y,z,dotsx, y, z, \ldots for first-order (number) variables and X,Y,Z,dotsX, Y, Z, \ldots for second-order (set) variables. An L_(2)\mathscr{L}_{2}-formula varphi\varphi is said to be bounded or Sigma_(0)^(0)\Sigma_{0}^{0} if it does not contain any second-order quantifiers and all first-order quantifiers are of the form AA x <= t\forall x \leq t or EE x <= t\exists x \leq t, and it is said to be Sigma_(n)^(0)(:}\Sigma_{n}^{0}\left(\right. resp. Pi_(n)^(0)\Pi_{n}^{0} ) if it is of the form EEx_(1)AAx_(2)dots Qx_(n)theta\exists x_{1} \forall x_{2} \ldots Q x_{n} \theta (resp. AAx_(1)EEx_(2)dots Qx_(n)theta\forall x_{1} \exists x_{2} \ldots Q x_{n} \theta ) where theta\theta is Sigma_(0)^(0)\Sigma_{0}^{0}. An L_(2)\mathscr{L}_{2}-formula varphi\varphi is said to be arithmetical or Sigma_(0)^(1)\Sigma_{0}^{1} if it does not contain any secondorder quantifiers, and it is said to be Sigma_(n)^(1)\Sigma_{n}^{1} (resp. Pi_(n)^(1)\Pi_{n}^{1} ) if it is of the form EEX_(1)AAX_(2)dots QX_(n)theta\exists X_{1} \forall X_{2} \ldots Q X_{n} \theta (resp. AAX_(1)EEX_(2)dots QX_(n)theta\forall X_{1} \exists X_{2} \ldots Q X_{n} \theta ) where theta\theta is Sigma_(0)^(1)\Sigma_{0}^{1}. If a Sigma_(n)^(0)\Sigma_{n}^{0}-formula (resp. Pi_(n)^(0)\Pi_{n}^{0}-formula) varphi\varphi does not contain any set variables (i.e., varphi\varphi is an L_(1)\mathscr{L}_{1}-formula), it is said to be Sigma_(n)\Sigma_{n} (resp. Pi_(n)\Pi_{n} ). We can extend L_(1)\mathscr{L}_{1} with unary relation symbols vec(U)=U_(1),dots,U_(k)\vec{U}=U_{1}, \ldots, U_{k}. Here, we identify U_(i)U_{i} 's as secondorder (set) constants and consider L_(1)uu vec(U)\mathscr{L}_{1} \cup \vec{U}-formulas as Sigma_(0)^(1)\Sigma_{0}^{1}-formulas (with extra constants). Then, an L_(1)uu vec(U)\mathscr{L}_{1} \cup \vec{U}-formula is said to be Sigma_(n)^( vec(U))\Sigma_{n}^{\vec{U}} (resp. Pi_(n)^( vec(U))\Pi_{n}^{\vec{U}} ) if it is Sigma_(n)^(0)\Sigma_{n}^{0} (resp. Pi_(n)^(0)\Pi_{n}^{0} ).
For our discussions, we need to distinguish the actual ("standard") natural numbers from natural numbers formalized in axiomatic systems. Here, we use ℜ\Re for the set of standard natural numbers, and N\mathbb{N} for natural numbers formalized in the system. When we write
" n=2,3,4,dotsn=2,3,4, \ldots, " it is intended that nn ranges over N\mathfrak{N} and n >= 2n \geq 2, while " n >= 2n \geq 2 " means that nn ranges over N\mathbb{N} and n >= 2n \geq 2.
2.1. The Paris-Harrington principle in first-order arithmetic
We adopt the elementary function arithmetic (EFA) for our base system of first-order arithmetic. It consists of the axioms of discrete ordered semirings, the totality of exponentiation ^(1){ }^{1} and the induction axiom (IND) of the form
(IND) varphi(0)^^AA x(varphi(x)rarr varphi(x+1))rarr AA x varphi(x)\varphi(0) \wedge \forall x(\varphi(x) \rightarrow \varphi(x+1)) \rightarrow \forall x \varphi(x)
for each Sigma_(0)\Sigma_{0}-formula varphi(x)\varphi(x). Then, the system ISigma_(n)I \Sigma_{n} is defined as EFA plus the induction axioms for Sigma_(n)\Sigma_{n}-formulas, and the Peano arithmetic (PA) is defined as PA =uuu_(n inOmega)ISigma_(n)=\bigcup_{n \in \mathfrak{\Omega}} I \Sigma_{n}. We may also expand EFA with unary predicates. If vec(U)=U_(1),dots,U_(k)\vec{U}=U_{1}, \ldots, U_{k} are unary predicates, EFA vec(U)\vec{U} consists of EFA plus the induction axioms for Sigma_(0)^( vec(U))\Sigma_{0}^{\vec{U}}-formulas.
Within EFA, finite sets of natural numbers, finite sequences of natural numbers, functions on finite sets, or other finite objects on N\mathbb{N} are coded by numbers. We write [N]^( < N)[\mathbb{N}]^{<\mathbb{N}} for the set of all (codes) of finite subsets of N\mathbb{N}. For each F in[N]^( < N)F \in[\mathbb{N}]^{<\mathbb{N}}, we can define |F||F| as the (unique) smallest m inNm \in \mathbb{N} such that there is a bijection between FF and m=[0,m)_(N)m=[0, m)_{\mathbb{N}}. In the context of the Ramsey theorem, a function of the form c:[X]^(n)rarr kc:[X]^{n} \rightarrow k is often called a coloring. (Recall that [X]^(n)={F in[N]^( < N):|F|=n^^F subeN}[X]^{n}=\left\{F \in[\mathbb{N}]^{<\mathbb{N}}:|F|=n \wedge F \subseteq \mathbb{N}\right\}.) Then, a set H sube XH \subseteq X is said to be cc-homogeneous if there exists i < ki<k such that [H]^(n)subec^(-1)(i)[H]^{n} \subseteq c^{-1}(i).
We first define the key notion introduced by Paris [32]. The following definition can be made within EFA.
Definition 2.1 (Density). Let n >= 1n \geq 1 or n=oon=\infty and k >= 2k \geq 2 or k=ook=\infty. For given m inNm \in \mathbb{N}, we define mm-density for (n,k)(n, k) as follows:
a finite set FF is said to be 0 -dense (n,k)(n, k) if |F| > min F|F|>\min F ( FF is relatively large),
a finite set FF is said to be (m+1)(m+1)-dense (n,k)(n, k) if for any c:[F]^(n^('))rarrk^(')c:[F]^{n^{\prime}} \rightarrow k^{\prime} where n^(') <= min{n,min F}n^{\prime} \leq \min \{n, \min F\} and k^(') <= min{k,min F}k^{\prime} \leq \min \{k, \min F\}, there exists a cc-homogeneous set H sube FH \subseteq F such that HH is mm-dense (n,k)(n, k). (Here, we set min{oo,a}=a\min \{\infty, a\}=a for a inNa \in \mathbb{N}.)
Although the notion is defined inductively, the statement that FF is mm-dense (n,k)(n, k) is Sigma_(0)\Sigma_{0}, in other words, there exists a Sigma_(0)\Sigma_{0}-formula psi(n,k,F,m)\psi(n, k, F, m) such that psi(n,k,F,m)\psi(n, k, F, m) holds if and only if FF is mm-dense (n,k)(n, k).
Definition 2.2 (The Paris-Harrington principle). Let n >= 1n \geq 1 or n=oo,k >= 2n=\infty, k \geq 2 or k=ook=\infty and m inNm \in \mathbb{N}. Then, the Paris-Harrington principle, mPH_(k)^(n)m \mathrm{PH}_{k}^{n} and ItPH_(k)^(n)\mathrm{ItPH}_{k}^{n}, is defined as follows:
mPH_(k)^(n):AA a EE b >= a([a,b)_(N):}m \mathrm{PH}_{k}^{n}: \forall a \exists b \geq a\left([a, b)_{\mathbb{N}}\right. is mm-dense {:(n,k))\left.(n, k)\right).
ItPH_(k)^(n):≡AA mmPH_(k)^(n)\mathrm{ItPH}_{k}^{n}: \equiv \forall m m \mathrm{PH}_{k}^{n}.
We simply write PH_(k)^(n)\mathrm{PH}_{k}^{n} for 1PH_(k)^(n)1 \mathrm{PH}_{k}^{n}. Additionally, we usually omit oo\infty and write PH^(n)\mathrm{PH}^{n} for PH_(oo)^(n)\mathrm{PH}_{\infty}^{n}, PH\mathrm{PH} for PH_(oo)^(oo)\mathrm{PH}_{\infty}^{\infty}, and so on.
It is known that ISigma_(1)I \Sigma_{1} proves PH_(2)^(n+1)rarrPH^(n)\mathrm{PH}_{2}^{n+1} \rightarrow \mathrm{PH}^{n}. Thus there is a hierarchy of implications
It is known that this hierarchy is strict above PH^(2)\mathrm{PH}^{2} over ISigma_(1)I \Sigma_{1}, whereas ISigma_(n)I \Sigma_{n} proves PH_(k)^(n+1)\mathrm{PH}_{k}^{n+1} for k=2,3,dotsk=2,3, \ldots On the other hand, calibrating the strength of mPH_(k)^(n)m \mathrm{PH}_{k}^{n} for m >= 2m \geq 2 is much harder, except for the implication mPH_(2)^(n)rarrPH_(m+1)^(n)m \mathrm{PH}_{2}^{n} \rightarrow \mathrm{PH}_{m+1}^{n} which directly follows from the definition.
We next formalize the correctness of theories of arithmetic. Within EFA, basic notions of first-order logic such as (well-formed) formulas, formal proofs (by the Hilbertstyle proof system or other formal systems) are formalizable by means of Gödel numbering. Typically, we can encode the provability for first- and second-order arithmetic within EFA, namely, there exists a Sigma_(1)\Sigma_{1}-formula Prov(T,x)\operatorname{Prov}(T, x) which means that a formula (encoded by) xx is provable from a theory (i.e., a finite or recursive set of sentences) T.^(2)T .{ }^{2} On the other hand, we can also formalize the truth on N\mathbb{N}, but only partially. By formalizing Tarski's truth definition, for each tuples of variables vec(Z)\vec{Z} and vec(z)\vec{z}, there exists a Pi_(1)^(0)\Pi_{1}^{0}-formula pi( vec(Z), vec(z),x)\pi(\vec{Z}, \vec{z}, x) such that for any unary predicates vec(U)\vec{U} and a Sigma_(0)^( vec(U))\Sigma_{0}^{\vec{U}}-formula varphi( vec(z))\varphi(\vec{z}), EFA vec(U)\vec{U} proves AA vec(z)(pi( vec(U), vec(z),|~varphi~|)harr varphi( vec(z)))\forall \vec{z}(\pi(\vec{U}, \vec{z},\lceil\varphi\rceil) \leftrightarrow \varphi(\vec{z})) where |~varphi~|\lceil\varphi\rceil is the Gödel number encoding varphi\varphi. Then, for n=1,2,dotsn=1,2, \ldots, there exists a Pi_(n)^(0)\Pi_{n}^{0}-formula Tr_(n)( vec(Z), vec(z),x)\operatorname{Tr}_{n}(\vec{Z}, \vec{z}, x) such that for any unary predicates vec(U)\vec{U} and a Pi_(n)^( vec(U))\Pi_{n}^{\vec{U}}-formula varphi( vec(z)),EFA vec(U)\varphi(\vec{z}), \operatorname{EFA} \vec{U} proves AA vec(z)(Tr_(n)(( vec(U)),( vec(z)),|~varphi~|)harr varphi(( vec(z))))\forall \vec{z}\left(\operatorname{Tr}_{n}(\vec{U}, \vec{z},\lceil\varphi\rceil) \leftrightarrow \varphi(\vec{z})\right). This formula is called the Pi_(n)\Pi_{n}-truth predicate. The formalized correctness statements (also known as reflection principles) are defined as follows. (Formally, pi\pi and Tr_(n)\operatorname{Tr}_{n} depend on the number of variables, but we may assume that vec(Z)\vec{Z} and vec(z)\vec{z} contains all variables which will appear in the entire discussion. We may ignore variables not appearing in the formula encoded by xx by substituting 0 into them.)
Definition 2.3 (Correctness). Let n=1,2,dotsn=1,2, \ldots, and let TT be an L_(1)\mathscr{L}_{1} - or L_(2)\mathscr{L}_{2}-theory. Then the Pi_(n)\Pi_{n}-correctness of T(Pi_(n):}T\left(\Pi_{n}\right.-corr {:(T))\left.(T)\right) is the following statement:
AA x\forall x (“ xx is (a Gödel number of) a Pi_(n)\Pi_{n}-sentence" ^^Prov(T,x)rarrTr_(n)(x)\wedge \operatorname{Prov}(T, x) \rightarrow \operatorname{Tr}_{n}(x) ).
Note that Pi_(n)\Pi_{n}-corr (T)(T) is a Pi_(n)\Pi_{n}-statement, and it implies the consistency of TT since it implies not(0=1)rarr not Prov(T,|~0=1~|)\neg(0=1) \rightarrow \neg \operatorname{Prov}(T,\lceil 0=1\rceil).
Now we are ready to state the theorem by Paris and Harrington.
Theorem 2.1 (Paris and Harrington [32,33]). The following are equivalent over Sigma_(1)^(3)\Sigma_{1}{ }^{3} :
1. PH\mathrm{PH}.
2. ItPH_(k)^(n)(n=3,4,dots,k=2,3,dots\operatorname{ItPH}_{k}^{n}(n=3,4, \ldots, k=2,3, \ldots or k=oo)k=\infty).
3. Pi_(2)\Pi_{2}-corr(PA).
Here, ItPH_(2)^(3)\mathrm{ItPH}_{2}^{3} is the original statement independent of PA introduced by Paris [32]. The equivalence of ItPH_(2)^(3)\mathrm{ItPH}_{2}^{3} and PH\mathrm{PH} can be proved in a combinatorial way, while we see that both are equivalent to Pi_(2)\Pi_{2}-corr(PA) in Section 5. Moreover, the Pi_(2)\Pi_{2}-correctness of fragments of PA can be characterized by PH as well.
Theorem 2.2 (Paris, see [16]). Let n=1,2,dotsn=1,2, \ldots Then Pi_(2)\Pi_{2}-corr( (Sigma_(n))\left(\Sigma_{n}\right) is equivalent to PH^(n+1)\mathrm{PH}^{n+1}over∣Sigma_(1)\operatorname{over} \mid \Sigma_{1}.
There are many other combinatorial or other numerical principles known to be independent of PA such as the Kanamori-McAloon theorem (KM) [20] and the termination of the Goodstein sequence [15]. Many of them are equivalent to the Pi_(2)\Pi_{2}-correctness of PA, while some others are strictly stronger. A typical such example is a finite variant of Kruskal's tree theorem introduced by Friedman. See [13,38][13,38].
2.2. Second-order arithmetic and the infinite Ramsey theorem
The system of second-order induction ISigma_(n)^(i)I \Sigma_{n}^{i} consists of EFA plus the induction axioms for Sigma_(n)^(i)\Sigma_{n}^{i}-formulas. It is not difficult to see that ∣Sigma_(n)^(0)\mid \Sigma_{n}^{0} is a conservative extension of ISigma_(n)I \Sigma_{n}, in other words, they prove the same L_(1)\mathscr{L}_{1}-sentences. Our base system for second-order arithmetic is RCA_(0)\mathrm{RCA}_{0}, which consists of ∣Sigma_(1)^(0)\mid \Sigma_{1}^{0} plus the following recursive comprehension axiom (RCA): for each pair of Sigma_(1)^(0)\Sigma_{1}^{0}-formulas varphi(x),psi(x)\varphi(x), \psi(x),
AA x(varphi(x)harr not psi(x))rarr EE X AA x(x in X harr varphi(x))\forall x(\varphi(x) \leftrightarrow \neg \psi(x)) \rightarrow \exists X \forall x(x \in X \leftrightarrow \varphi(x))
The next system is WKL_(0)\mathrm{WKL}_{0}, which consists of RCA_(0)\mathrm{RCA}_{0} plus weak König's lemma (WKL). Here, we define WKL\mathrm{WKL} in a slightly stronger form (but still equivalent to the original definition over RCA_(0)\operatorname{RCA}_{0}, see [39, LEMMA IV.1.4]). A tree TT is a family of functions of the form p:[0,m)_(N)rarrNp:[0, m)_{\mathbb{N}} \rightarrow \mathbb{N} ( m inNm \in \mathbb{N} ) such that for any p in Tp \in T and ℓinN\ell \in \mathbb{N} with [[0,ℓ)_(N)]^(n)sube dom(p),p↾[[0,ℓ)_(N)]^(n)\left[[0, \ell)_{\mathbb{N}}\right]^{n} \subseteq \operatorname{dom}(p), p \upharpoonright\left[[0, \ell)_{\mathbb{N}}\right]^{n} is also a member of TT. A tree TT is said to be bounded if there exists a function h:NrarrNh: \mathbb{N} \rightarrow \mathbb{N} such that p(i) <= h(i)p(i) \leq h(i) for any p in Tp \in T and i in dom(p)i \in \operatorname{dom}(p). Then WKL asserts the following:
for any infinite bounded tree TT, there exists a function (a path of TT ) ff such that f↾[0,m)_(N)in Tf \upharpoonright[0, m)_{\mathbb{N}} \in T for any m inNm \in \mathbb{N}.
Finally, the system A_(0)A_(0)A_{0} A_{0} consists of RCA_(0)\mathrm{RCA}_{0} plus the arithmetical comprehension axiom (ACA): for each Sigma_(0)^(1)\Sigma_{0}^{1}-formula varphi(x)\varphi(x),
EE X AA x(x in X harr varphi(x))\exists X \forall x(x \in X \leftrightarrow \varphi(x))
The strength of these three systems is precisely known and WKL_(0)\mathrm{WKL}_{0} is strictly inbetween RCA_(0)R C A_{0} and ACA_(0)A C A_{0}. On the other hand, the L_(1)\mathscr{L}_{1}-consequences of RCA_(0)R C A_{0} and WKL_(0)W K L_{0} are the same and they coincide with those of ISigma_(1)I \Sigma_{1}, while the LL_(1)\mathscr{L} \mathscr{L}_{1}-consequences of ACA_(0)\mathrm{ACA}_{0} coincide with those of PA.
Over RCA , the infinite Ramsey theorem is directly formalizable as follows.
Definition 2.4 (The infinite Ramsey theorem). The infinite Ramsey theorem RT_(k)^(n)\mathrm{RT}_{k}^{n} is defined as follows:
RT_(k)^(n)\mathrm{RT}_{k}^{n} : for any c:[N]^(n)rarr kc:[\mathbb{N}]^{n} \rightarrow k, there exists an infinite set H subeNH \subseteq \mathbb{N} such that HH is cc-homogeneous ( n >= 1n \geq 1 and k >= 2k \geq 2 ).
RT_(oo)^(n):≡AA kRT_(k)^(n),RT_(oo)^(oo):≡AA nRT_(oo)^(n)\mathrm{RT}_{\infty}^{n}: \equiv \forall k \mathrm{RT}_{k}^{n}, \mathrm{RT}_{\infty}^{\infty}: \equiv \forall n \mathrm{RT}_{\infty}^{n}.
We usually omit oo\infty and write RT^(n)\mathrm{RT}^{n} for RT_(oo)^(n),RT^(2)\mathrm{RT}_{\infty}^{n}, \mathrm{RT}^{2} for RT_(oo)^(oo)\mathrm{RT}_{\infty}^{\infty}.
Within RCA_(0)\mathrm{RCA}_{0}, it is known that RT_(k)^(n)\mathrm{RT}_{k}^{n} implies RT_(k+1)^(n)\mathrm{RT}_{k+1}^{n} and RT_(2)^(n+1)\mathrm{RT}_{2}^{n+1} implies RT^(n)\mathrm{RT}^{n}. Be aware that the former does not imply RT_(2)^(n)rarrRT^(n)\mathrm{RT}_{2}^{n} \rightarrow \mathrm{RT}^{n} because of the lack of induction. So, we have the hierarchy
However, this hierarchy collapses at the level of n=3n=3.
Theorem 2.3 (Jockusch [19], reformulated by Simpson [39]). Let n=3,4,dotsn=3,4, \ldots, and let k=2,3,dotsk=2,3, \ldots or k=ook=\infty. Then, over RCA_(0),RT_(k)^(n)\mathrm{RCA}_{0}, \mathrm{RT}_{k}^{n} is equivalent to ACA_(0)\mathrm{ACA}_{0}.
On the other hand, the full infinite Ramsey theorem RT is strictly stronger than ACA_(0)\mathrm{ACA}_{0}. This is unavoidable since RT implies PH over RCA_(0)\mathrm{RCA}_{0}, and thus it implies the consistency of PA. To prove RT, we need the system ACA_(0)^(')\mathrm{ACA}_{0}^{\prime} which consists of ACA_(0)\mathrm{ACA}_{0} plus the assertion that for any n inNn \in \mathbb{N} and any set XX, the nnth Turing jump of XX exists.
Theorem 2.4 (McAloon [29], see also [17]). Over RCA , RT is equivalent to ACA_(0)^(')\mathrm{ACA}_{0}^{\prime}.
The situations of RT_(2)^(2)\mathrm{RT}_{2}^{2} and RT^(2)\mathrm{RT}^{2} are complicated. There are many important results on the reverse mathematical and computability theoretic strength of RT_(2)^(2)\mathrm{RT}_{2}^{2} or RT^(2)\mathrm{RT}^{2} such as [7,8,30,37][7,8,30,37]. Typically, RT_(2)^(2)\mathrm{RT}_{2}^{2} and RT^(2)\mathrm{RT}^{2} are strictly in between RCA_(0)\mathrm{RCA}_{0} and ACA_(0)\mathrm{ACA}_{0}, but still different from WKL_(0)\mathrm{WKL}_{0} even with full induction.
Theorem 2.5 (Jockusch [19], Liu [28]). RT_(2)^(2)\mathrm{RT}_{2}^{2} and RT^(2)\mathrm{RT}^{2} are incomparable with WKL_(0)\mathrm{WKL}_{0} over RCA_(0)+∣Sigma_(oo)^(1)(:}\operatorname{RCA}_{0}+\mid \Sigma_{\infty}^{1}\left(\right. where ∣Sigma_(oo)^(i)={ISigma_(n)^(i):n in Omega}\mid \Sigma_{\infty}^{i}=\left\{I \Sigma_{n}^{i}: n \in \Omega\right\} ).
The Pi_(1)^(1)\Pi_{1}^{1}-consequences (or equivalently, L_(1)\mathscr{L}_{1}-consequences with second-order constants) of RT_(2)^(2)\mathrm{RT}_{2}^{2} and RT^(2)\mathrm{RT}^{2} are also studied precisely. APi_(n)^(1)\mathrm{A} \Pi_{n}^{1}-formula AAX_(1)dots QX_(n)theta\forall X_{1} \ldots Q X_{n} \theta is said to be restricted Pi_(n)^(1)(rPi_(n)^(1))\Pi_{n}^{1}\left(\mathrm{r} \Pi_{n}^{1}\right) if theta\theta is Sigma_(2)^(0)\Sigma_{2}^{0} and nn is odd or theta\theta is Pi_(2)^(0)\Pi_{2}^{0} and nn is even, and rSigma_(n)^(1)\mathrm{r} \Sigma_{n}^{1}-formulas are defined in the dual way.
Theorem 2.6. 1. RCA_(0)+RT_(2)^(2)\mathrm{RCA}_{0}+\mathrm{RT}_{2}^{2} proves BSigma_(2)^(0)\mathrm{B} \Sigma_{2}^{0} and it is Pi_(1)^(1)\Pi_{1}^{1}-conservative over RCA_(0)+ISigma_(2)^(0)\mathrm{RCA}_{0}+\mathrm{I} \Sigma_{2}^{0} (i.e., any Pi_(1)^(1)\Pi_{1}^{1}-sentences which are provable from RCA_(0)+RT_(2)^(2)\mathrm{RCA}_{0}+\mathrm{RT}_{2}^{2} are provable from RCA_(0)+ISigma_(2)^(0)\mathrm{RCA}_{0}+\mathrm{I} \Sigma_{2}^{0} ). (Hirst [18] and Cholak/Jockusch/Slaman [7] )^(4))^{4}
2. RCA_(0)+RT_(2)^(2)\mathrm{RCA}_{0}+\mathrm{RT}_{2}^{2} is rPi_(1)^(1)\mathrm{r} \Pi_{1}^{1}-conservative over RCA_(0)\mathrm{RCA}_{0}. (Patey/Yokoyama [34], see also Kołodziejczyk/Yokoyama [25])
3. RCA_(0)+RT^(2)\mathrm{RCA}_{0}+\mathrm{RT}^{2} proves BSigma_(3)^(0)\mathrm{B} \Sigma_{3}^{0} and it is Pi_(1)^(1)\Pi_{1}^{1}-conservative over RCA_(0)+BSigma_(3)^(0)\mathrm{RCA}_{0}+B \Sigma_{3}^{0}. (Hirst [18] and Slaman/Yokoyama [40])
4BSigma_(n)^(0)4 \mathrm{~B} \Sigma_{n}^{0} is called a bounding principle, see [16] for the definition
The above theorem decides the consistency strength (or proof-theoretic strength) of RT_(2)^(2)\mathrm{RT}_{2}^{2} and RT^(2)\mathrm{RT}^{2}, and more precise studies have been carried out for RT_(2)^(2)\mathrm{RT}_{2}^{2} with respect to the size of proofs [24,25]. However, the exact L_(1)\mathscr{L}_{1}-consequences of RCA_(0)+RT_(2)^(2)\mathrm{RCA}_{0}+\mathrm{RT}_{2}^{2} are still not identified. Meanwhile, several hybrid approaches of computability and proof/model-theory are currently being developed such as [9,10][9,10] which may help to calibrate the L_(1)\mathscr{L}_{1}-consequences of various combinatorial principles.
3. THE PARIS-HARRINGTON PRINCIPLE IN SECOND-ORDER ARITHMETIC
In this section, we consider the Paris-Harrington principle in the setting of secondorder arithmetic. The main difference is that we can now consider the Paris-Harrington principle within an infinite set. Then, Theorems 2.1 and 2.2 are reformulated as Theorems 3.2-3.6.
3.1. Second-order formulations of PH\mathbf{P H}
Recall that PH_(k)^(n)\mathrm{PH}_{k}^{n} asserts that there exists an arbitrary large finite set which is 1-dense (n,k)(n, k). Indeed, a 1-dense (n,k)(n, k) set should exist within any infinite subset of N\mathbb{N} by the infinite Ramsey theorem (see the proof of Proposition 3.1 below). We reformulate PH_(k)^(n)\mathrm{PH}_{k}^{n} based on this idea in second-order arithmetic.
Definition 3.1 (The Paris-Harrington principle, second-order form). Let n >= 1n \geq 1 or n=oon=\infty, k >= 2k \geq 2 or k=ook=\infty and m inNm \in \mathbb{N}. Then, the Paris-Harrington principle, m bar(PH)_(k)^(n)m \overline{\mathrm{PH}}_{k}^{n} and It bar(PH)_(k)^(n)\mathrm{It} \overline{\mathrm{PH}}_{k}^{n}, is defined as follows:
m bar(PH)_(k)^(n)m \overline{\mathrm{PH}}_{k}^{n} : for any infinite set X_(0)X_{0}, there exists a finite set F subeX_(0)F \subseteq X_{0} such that FF is mm-dense (n,k)(n, k).
It bar(PH)_(k)^(n):≡AA mm bar(PH)_(k)^(n)\mathrm{It} \overline{\mathrm{PH}}_{k}^{n}: \equiv \forall m m \overline{\mathrm{PH}}_{k}^{n}.
Just like for PH\mathrm{PH}, we write bar(PH)_(k)^(n)\overline{\mathrm{PH}}_{k}^{n} for 1 bar(PH)_(k)^(n), bar(PH)^(n)1 \overline{\mathrm{PH}}_{k}^{n}, \overline{\mathrm{PH}}^{n} for bar(PH)_(oo)^(n)\overline{\mathrm{PH}}_{\infty}^{n}, and so on.
We first see that any of these variants of the Paris-Harrington theorem are true since they are consequences of the infinite Ramsey theorem by the following "compactness" argument.
For given n >= 1n \geq 1 and k >= 2k \geq 2, an (n,k)(n, k)-coloring tree TT on a set XX is a family of functions of the form p:[m nn X]^(n)rarr k(m inN)p:[m \cap X]^{n} \rightarrow k(m \in \mathbb{N}) such that for any p in Tp \in T and ℓinN\ell \in \mathbb{N} with [ℓnn X]^(n)sube dom(p),p↾[ℓnn X]^(n)[\ell \cap X]^{n} \subseteq \operatorname{dom}(p), p \upharpoonright[\ell \cap X]^{n} is also a member of TT. Then, WKL_(0)\mathrm{WKL}_{0} proves that any infinite (n,k)(n, k)-coloring tree TT on an infinite set XX has a path f:[X]^(n)rarr kf:[X]^{n} \rightarrow k in the sense that f↾[m nn X]^(n)in Tf \upharpoonright[m \cap X]^{n} \in T for any m inNm \in \mathbb{N}.
Proposition 3.1. Let n >= 1n \geq 1 or n=oo,k >= 2n=\infty, k \geq 2 or k=ook=\infty and m inNm \in \mathbb{N}. WKL_(0)+RT_(k)^(n)\mathrm{WKL}_{0}+\mathrm{RT}_{k}^{n} proves m bar(PH)_(k)^(n)rarr m+1 bar(PH)_(k)^(n)m \overline{\mathrm{PH}}_{k}^{n} \rightarrow m+1 \overline{\mathrm{PH}}_{k}^{n}. In particular, WKL_(0)+RT_(k)^(n)\mathrm{WKL}_{0}+\mathrm{RT}_{k}^{n} proves bar(PH)_(k)^(n)\overline{\mathrm{PH}}_{k}^{n}, and WKL_(0)+RT_(k)^(n)+ISigma_(1)^(1)\mathrm{WKL}_{0}+\mathrm{RT}_{k}^{n}+\mathrm{I} \Sigma_{1}^{1} proves It bar(PH)_(k)^(n)\mathrm{It} \overline{\mathrm{PH}}_{k}^{n}.
Proof. We prove for the case n >= 1n \geq 1 and k >= 2k \geq 2. Assume that m+1 bar(PH)_(k)^(n)m+1 \overline{\mathrm{PH}}_{k}^{n} fails on some infinite set XX. Let TT be an (n,k)(n, k)-coloring tree on XX such that p in Tp \in T if and only if there is no pp homogeneous set which is mm-dense (n,k)(n, k). Then, TT is infinite since any finite subset of XX is not m+1m+1-dense (n,k)(n, k), and thus it has a path f:[X]^(n)rarr kf:[X]^{n} \rightarrow k. By RT _(k)^(n){ }_{k}^{n}, there is an infinite set H sube XH \subseteq X which is ff-homogeneous. Then mPH_(k)^(n)m \mathrm{PH}_{k}^{n} fails on HH by the definition of ff.
Proving bar(PH)_(k)^(n)\overline{\mathrm{PH}}_{k}^{n} just from the induction is much harder, but if n=1,2,dots,∣Sigma_(n)^(0)n=1,2, \ldots, \mid \Sigma_{n}^{0} still proves bar(PH)_(k)^(n+1)\overline{\mathrm{PH}}_{k}^{n+1} for k=2,3,dotsk=2,3, \ldots On the other hand, stronger induction does not help with the absence of the infinite Ramsey theorem. Indeed, RCA_(0)+ISigma_(oo)^(1)\mathrm{RCA}_{0}+I \Sigma_{\infty}^{1} does not prove bar(PH)\overline{\mathrm{PH}} or even PH. ^(5){ }^{5}
Within RCA _(0){ }_{0}, the statement of rPi_(n)^(1)\mathrm{r} \Pi_{n}^{1}-correctness of a theory T(rPi_(n)^(1):}T\left(\mathrm{r} \Pi_{n}^{1}\right. - {: corr(T))\left.\operatorname{corr}(T)\right) can be defined like in Definition 2.3, and rPi_(n)^(1)\mathrm{r} \Pi_{n}^{1} - corr(T)\operatorname{corr}(T) is an rPi_(n)^(1)\mathrm{r} \Pi_{n}^{1}-statement. Second-order versions of the Paris-Harrington principle are closely related to rPi_(1)^(1)\mathrm{r} \Pi_{1}^{1}-correctness of the infinite Ramsey theorem and other systems, and also related to well-orderedness of ordinals, which is naturally formalizable within RCA_(0)\mathrm{RCA}_{0}. Here we summarize the relations between the ParisHarrington principles, rPi_(1)^(1)\mathrm{r} \Pi_{1}^{1}-correctness and well-foundedness of ordinals.
Theorem 3.2. The following are equivalent over RCA_(0)\mathrm{RCA}_{0} :
bar(PH)^(2)\overline{\mathrm{PH}}^{2}.
It bar(PH)_(2)^(2)\mathrm{It} \overline{\mathrm{PH}}_{2}^{2}.
5 Indeed, WKL_(0)+ISigma_(oo)^(1)W K L_{0}+I \Sigma_{\infty}^{1} is a Pi_(1)^(1)\Pi_{1}^{1}-conservative extension of RCA_(0)+ISigma_(oo)^(0)R C A_{0}+I \Sigma_{\infty}^{0}.
Theorem 3.5. The following are equivalent over RCA_(0)\mathrm{RCA}_{0} :
bar(PH)\overline{\mathrm{PH}}.
It bar(PH)_(k)^(n)(n=3,4,dots,k=2,3,dots,oo)\operatorname{It} \overline{\mathrm{PH}}_{k}^{n}(n=3,4, \ldots, k=2,3, \ldots, \infty).
Theorem 3.6. Over RCA_(0)\mathrm{RCA}_{0}, It bar(PH)\mathrm{It} \overline{\mathrm{PH}} is equivalent to rPi_(1)^(1)-corr(ACA_(0)^('))\mathrm{r} \Pi_{1}^{1}-\operatorname{corr}\left(\mathrm{ACA}_{0}^{\prime}\right).
Over ACA_(0)\mathrm{ACA}_{0}, any Pi_(1)^(1)\Pi_{1}^{1}-formula is equivalent to a rPi_(1)^(1)\mathrm{r} \Pi_{1}^{1}-formula. Thus, ACA_(0)+ bar(PH)\mathrm{ACA}_{0}+\overline{\mathrm{PH}} implies Pi_(n)\Pi_{n}-corr(PA) for any n inNn \in \mathfrak{N}, in other words, the L_(1)\mathscr{L}_{1}-correctness schema of PA.
Many of the equivalences in the above theorems have been known to experts in one formulation or another for a long time, although at least some of them are hard to find in the literature. On the other hand, 3harr43 \leftrightarrow 4 of Theorems 3.2 and 3.3 are more recent, and not easy since they correspond to the study of the first-order strength of the infinite Ramsey theorem for pairs, which we have seen in Theorem 2.6. The equivalences between variants of PH\mathrm{PH} and the well-orderedness of ordinals are obtained by measuring the largeness of finite sets using ordinals, as presented in the next subsection. In Section 5, we explain how to prove the equivalences between variants of PH\mathrm{PH} and the correctness statements by the method of indicators.
3.2. PH and the notion of alpha\alpha-largeness
The Paris-Harrington principle is closely related to a notion of largeness for finite sets defined using ordinals. In [22], Ketonen and Solovay introduced the notion of alpha\alpha-largeness for ordinal alpha < epsi_(0)\alpha<\varepsilon_{0} and calibrated how large set is needed for PH\mathrm{PH}.
Definition 3.2 ( alpha\alpha-largeness, within RCA_(0)^(6)\operatorname{RCA}_{0}{ }^{6} ). For alpha < epsi_(0)\alpha<\varepsilon_{0} and m inNm \in \mathbb{N}, define alpha[m]=0\alpha[m]=0 if alpha=0\alpha=0, alpha[m]=beta\alpha[m]=\beta if alpha=beta+1,alpha[m]=beta+omega^(gamma)*m\alpha=\beta+1, \alpha[m]=\beta+\omega^{\gamma} \cdot m if alpha=beta+omega^(gamma+1)\alpha=\beta+\omega^{\gamma+1}, and alpha[m]=beta+omega^(gamma[m])\alpha[m]=\beta+\omega^{\gamma[m]} if alpha=beta+omega^(gamma)\alpha=\beta+\omega^{\gamma} and gamma\gamma is a limit ordinal. Then a finite set X={x_(0) < cdots < x_(â„“-1)}subeN({x_(i)}_(i):}X=\left\{x_{0}<\cdots<x_{\ell-1}\right\} \subseteq \mathbb{N}\left(\left\{x_{i}\right\}_{i}\right. is the increasing enumeration of XX ) is called alpha\alpha-large if alpha[x_(0)]dots[x_(â„“-1)]=0\alpha\left[x_{0}\right] \ldots\left[x_{\ell-1}\right]=0.
The well-foundedness of ordinals and the notion of alpha\alpha-largeness is closely related. Indeed, if alpha\alpha is well-founded and X={x_(0) < x_(1) < cdots}X=\left\{x_{0}<x_{1}<\cdots\right\} is infinite, then alpha[x_(0)][x_(1)]dots\alpha\left[x_{0}\right]\left[x_{1}\right] \ldots should terminate at 0 within finitely many steps, which means that XX contains an alpha\alpha-large set. It is not difficult to see the converse, and we have the following.
Proposition 3.7. Let alpha < epsi_(0)\alpha<\varepsilon_{0}. The following assertions are equivalent over RCA_(0)\mathrm{RCA}_{0} :
Any infinite set contains an alpha\alpha-large finite subset.
alpha\alpha is well-founded.
6 Indeed, this definition still works within EFA with primitive recursive descriptions of ordinals.
The relations between PH\mathrm{PH} and alpha\alpha-largeness are well-studied and have been the topic of ordinal analysis; see, e.g., [3-5,22,25,27,41][3-5,22,25,27,41]. Here we list several (digested) results from those papers. Let omega_(0)^(alpha)=alpha\omega_{0}^{\alpha}=\alpha and omega_(n+1)^(alpha)=omega^(omega_(n)^(alpha))\omega_{n+1}^{\alpha}=\omega^{\omega_{n}^{\alpha}}, and let omega_(n)=omega_(n)^(1)\omega_{n}=\omega_{n}^{1}.
Theorem 3.8. The following are provable within RCA_(0)\mathrm{RCA}_{0}. Let F subeNF \subseteq \mathbb{N} be a finite set with min F >= 3\min F \geq 3, and let n,k >= 1n, k \geq 1 and m >= 0m \geq 0.
If FF is omega^(k+4)\omega^{k+4}-large, then FF is 1-dense(2, kk ). (Ketonen/Solovay [22])
If FF is 1 -dense (2,k+1)(2, k+1), then FF is omega^(k)\omega^{k}-large. (folklore)
If FF is omega_(n)^(omega*k+1)\omega_{n}^{\omega \cdot k+1}-large, then FF is 1-dense (n+1,k)(n+1, k). (essentially [22])
If FF is 1 -dense (n+1,3^(n))\left(n+1,3^{n}\right), then FF is omega_(n)\omega_{n}-large. (Kotlarski/Piekart/Weiermann [27])
If FF is omega^(300^(m))\omega^{300^{m}}-large, then FF is mm-dense(2, 2). (Kołodziejczyk/Yokoyama [25])
Many implications of Theorems 3.2-3.5 follow from the above theorem. Indeed, 1harr2harr51 \leftrightarrow 2 \leftrightarrow 5 of Theorem 3.2 follows from statements 1,2 and 5 of the above, and 5rarr15 \rightarrow 1 of Theorem 3.3, 3rarr13 \rightarrow 1 of Theorem 3.4, and 1harr4rarr21 \leftrightarrow 4 \rightarrow 2 of Theorem 3.5 follow from statements 3,4 , and 6 . We see other implications in Section 5 .
Well-foundedness of ordinals is also heavily related with correctness statements and their relations are widely studied. For the recent developments, see, e.g., [1, 31].
4. GENERALIZATIONS OF PH
In this section, we see several generalizations of the Paris-Harrington principle by modifying the relative largeness condition " |H| > min H|H|>\min H." They are still natural strengthenings of the finite Ramsey theorem and quickly follow from the infinite Ramsey theorem and a compactness argument of the kind presented in Proposition 3.1. Nonetheless, a strong enough form of the Paris-Harrington principle recovers the infinite Ramsey theorem (Theorem 4.5) and its iterations provide the rPi_(2)^(1)\mathrm{r} \Pi_{2}^{1}-correctness of the infinite Ramsey theorem (Theorems 4.6-4.8).
4.1. Phase transition
A natural generalization of PH_(k)^(n)\mathrm{PH}_{k}^{n} would be provided by changing the relative largeness condition |H| > min H|H|>\min H to |H| > f(min H)|H|>f(\min H) for some function ff. We write PH_(k,f)^(n)\mathrm{PH}_{k, f}^{n} or bar(PH)_(k,f)^(n)\overline{\mathrm{PH}}_{k, f}^{n} for the statement defined as PH_(k)^(n)\mathrm{PH}_{k}^{n} or bar(PH)_(k)^(n)\overline{\mathrm{PH}}_{k}^{n} but with |H| > min H|H|>\min H replaced by |H| > f(min H)|H|>f(\min H). Unfortunately, this does not make PH stronger in most cases. Indeed, one can easily prove the following.
Proposition 4.1.
Let n=2,3,dotsn=2,3, \ldots or n=oon=\infty, and let ff be a primitive recursive function. Then 1Sigma_(1)+PH^(n)1 \Sigma_{1}+\mathrm{PH}^{n} proves PH_(f)^(n)\mathrm{PH}_{f}^{n}.
Let ff be a provably recursive function of PA\mathrm{PA}. Then ISigma_(1)+PH\mathrm{I} \Sigma_{1}+\mathrm{PH} proves PH_(f)\mathrm{PH}_{f}.
Let n=1,2,dotsn=1,2, \ldots or n=oon=\infty and let k=2,3,dotsk=2,3, \ldots or k=ook=\infty. Then RCA_(0)+ bar(PH)_(k)^(n)\mathrm{RCA}_{0}+\overline{\mathrm{PH}}_{k}^{n} proves that for any function f, bar(PH)_(k,f)^(n)f, \overline{\mathrm{PH}}_{k, f}^{n} holds.
On the other hand, PH_(f)\mathrm{PH}_{f} can be weaker if ff is slower growing than the identity function. Indeed, if ff is a constant function, then PH_(f)\mathrm{PH}_{f} is just the finite Ramsey theorem, and thus it is provable within PA. Weiermann [44] revealed the border of the provability and unprovability in this context as part of his research program called phase transition.
Theorem 4.2 (Weiermann [44]). Let log_(n)\log _{n} be the inverse function of the nth iterated exponential function exp^(n)(x)\exp ^{n}(x) where exp(x)=2^(x)\exp (x)=2^{x}, and let log_(**)\log _{*} be the inverse function of the superexponential (tower) function 2_(x)2_{x}.
PH_(log_(n))\mathrm{PH}_{\log _{n}} is not provable from PA\mathrm{PA} for any n >= 1n \geq 1.
PH_(log_(**))\mathrm{PH}_{\log _{*}} is provable from PA\mathrm{PA}.
A sharper border is revealed in [44], and similar analyses have been done for KM and other principles as well [35].
4.2. PH with generalized largeness
To obtain further generalization of PH\mathrm{PH}, we want to consider some condition of the form |H| > f(H)|H|>f(H) where ff assigns some "required size" for each finite set. Inspired by Terrence Tao's blog [43], Gaspar and Kohlenbach [14] introduced several "finitary" versions of the infinite pigeonhole principle ( RT^(1)\mathrm{RT}^{1} in our terminology) which are formulated based on this idea. Then, Pelupessy generalizes it to the infinite Ramsey theorem as follows.
Definition 4.1 (Gaspar/Kohlenbach [14], Pelupessy [36]). A function f:[N] < NrarrNf:[\mathbb{N}]<\mathbb{N} \rightarrow \mathbb{N} is said to be asymptotically stable if for any increasing sequence of finite sets F_(0)subeF_(1)sube dotsF_{0} \subseteq F_{1} \subseteq \ldots{f(F_(i))}_(i inN)\left\{f\left(F_{i}\right)\right\}_{i \in \mathbb{N}} converges. Then, the finitary infinite Ramsey theorem FIRT_(k)^(n)\mathrm{FIRT}_{k}^{n} states the following:
IIRT _(k)^(n)_{k}^{n} : for any asymptotically stable function f:[N]^( < N)rarrNf:[\mathbb{N}]^{<\mathbb{N}} \rightarrow \mathbb{N}, there exists r inNr \in \mathbb{N} such that for any c:[[0,r)_(N)]^(n)rarr kc:\left[[0, r)_{\mathbb{N}}\right]^{n} \rightarrow k, there exists a homogeneous set H sube[0,r)_(N)H \subseteq[0, r)_{\mathbb{N}} such that |H| > f(H)|H|>f(H).
FIRT_(oo)^(n)-=AA kFIRT_(k)^(n),FIRT_(oo)^(oo)-=AA nFIRT_(k)^(n)\operatorname{FIRT}_{\infty}^{n} \equiv \forall k \mathrm{FIRT}_{k}^{n}, \mathrm{FIRT}_{\infty}^{\infty} \equiv \forall n \mathrm{FIRT}_{k}^{n}.
The finitary infinite pigeonhole principle FIPP_(2)\mathrm{FIPP}_{2} in [14] is the same as FIRT_(oo)^(1)\mathrm{FIRT}_{\infty}^{1}.
Gaspar/Kohlenbach and Pelupessy showed that FIRT_(k)^(n)\mathrm{FIRT}_{k}^{n} is equivalent to RT_(k)^(n)\mathrm{RT}_{k}^{n} over WKL_(0)\mathrm{WKL}_{0} (we will see this in detail later). Thus, FIRT_(k)^(n)\mathrm{FIRT}_{k}^{n} could be considered as a "finitary" rephrasing of infinite combinatorics.
Remark 4.3. In [14], another form of the finitary infinite pigeonhole principle FIPP_(3)\mathrm{FIPP}_{3} is also studied, and the question is raised which is more appropriate as the finitary version of infinite
pigeonhole principle. However, FIPP_(3)\mathrm{FIPP}_{3} is equivalent to ACA_(0)\mathrm{ACA}_{0} [45], and it does not fit with the general form of the Ramsey theorem.
Then, can we consider more general statements? Remember that the original idea of the finite Ramsey theorem or the Paris-Harrington principle is that if a large enough set is given, one must find a homogeneous set which is still "large" in some sense. Here, we consider a general concept of largeness for finite sets as follows.
Definition 4.2 (Largeness notion). A family of finite sets Lsube[N]^( < N)\mathbb{L} \subseteq[\mathbb{N}]^{<\mathbb{N}} is said to be a prelargeness notion if it is upward closed, in other words, F_(0)inLF_{0} \in \mathbb{L} and F_(0)subeF_(1)F_{0} \subseteq F_{1} implies F_(1)inLF_{1} \in \mathbb{L}. A prelargeness notion L\mathbb{L} is said to be a largeness notion if for any infinite set X subeNX \subseteq \mathbb{N}, there exists a finite set F sube XF \subseteq X such that F inLF \in \mathbb{L}.
The idea of the above definition is that an infinite set is always large enough and thus it should contain a "large finite set" in the sense of L\mathbb{L}. For example, L_(omega)={F in\mathbb{L}_{\omega}=\{F \in{:[N]^( < N):|F| > min F}\left.[\mathbb{N}]^{<\mathbb{N}}:|F|>\min F\right\} is a largeness notion. Note that " L\mathbb{L} is a prelargeness notion" is just a Pi_(1)^(L)\Pi_{1}^{\mathbb{L}}-statement and thus it is available within EFA^(L)E F A^{\mathbb{L}}. On the other hand, " L\mathbb{L} is a largeness notion" is an rPi_(1)^(1)\mathrm{r} \Pi_{1}^{1}-statement, so it strictly requires the second-order language. Next, we generalize the density notion. The following definition can be made within EFA^(L)E F A^{\mathbb{L}}.
Definition 4.3 (Density with respect to L\mathbb{L} ). Let n >= 1n \geq 1 or n=oon=\infty and k >= 2k \geq 2 or k=ook=\infty. Let L\mathbb{L} be a prelargeness notion. We define the density for (n,k,L)(n, k, \mathbb{L}) as follows:
a finite set FF is said to be 0 -dense (n,k,L)(n, k, \mathbb{L}) if F inLF \in \mathbb{L},
a finite set FF is said to be m+1m+1-dense (n,k,L)(n, k, \mathbb{L}) if for any c:[F]^(n^('))rarrk^(')c:[F]^{n^{\prime}} \rightarrow k^{\prime} where n^(') <= min{n,min F}n^{\prime} \leq \min \{n, \min F\} and k^(') <= min{k,min F}k^{\prime} \leq \min \{k, \min F\}, there exists a cc-homogeneous set H sube FH \subseteq F such that HH is mm-dense (n,k,L)(n, k, \mathbb{L}).
The statement that FF is mm-dense (n,k,L)(n, k, \mathbb{L}) is Sigma_(0)^(L)\Sigma_{0}^{\mathbb{L}}.
Now we define the generalized Paris-Harrington principle. The following definition can be made within RCA .
Definition 4.4 (Generalized PH). Let n >= 1n \geq 1 or n=oo,k >= 2n=\infty, k \geq 2 or k=ook=\infty and m inNm \in \mathbb{N}. Then, the generalized Paris-Harrington principle, mGPH_(k)^(n)m \mathrm{GPH}_{k}^{n} and ItGPH_(k)^(n)\mathrm{ItGPH}_{k}^{n}, is defined as follows:
mGPH_(k)^(n)m \mathrm{GPH}_{k}^{n} : for any largeness notion L\mathbb{L} and for any infinite set X_(0)X_{0}, there exists a finite set F subeX_(0)F \subseteq X_{0} such that FF is mm-dense (n,k,L)(n, k, \mathbb{L}).
ItGPH_(k)^(n):≡AA mmGPH_(k)^(n)\mathrm{ItGPH}_{k}^{n}: \equiv \forall m m \mathrm{GPH}_{k}^{n}.
Just like for PH\mathrm{PH}, we write GPH_(k)^(n)\mathrm{GPH}_{k}^{n} for 1GPH_(k)^(n),GPH^(n)1 \mathrm{GPH}_{k}^{n}, \mathrm{GPH}^{n} for GPH_(oo)^(n)\mathrm{GPH}_{\infty}^{n} and so on.
Unlike bar(PH)_(k)^(n),GPH_(k)^(n)\overline{\mathrm{PH}}_{k}^{n}, \mathrm{GPH}_{k}^{n} is "iterable." Indeed, GPH_(k)^(n)\mathrm{GPH}_{k}^{n} states that if L\mathbb{L} is a largeness notion, then the family of all 1-dense (n,k,L)(n, k, \mathbb{L}) sets is also a largeness notion, and thus GPH_(k)^(n)\mathrm{GPH}_{k}^{n} can be applied to it again. Furthermore, any infinite subset X subeNX \subseteq \mathbb{N} is "isomorphic to N\mathbb{N} " in the following sense; if h:Nrarr Xh: \mathbb{N} \rightarrow X is a monotone increasing bijection and L\mathbb{L} is a largeness notion,
then h^(-1)(L)h^{-1}(\mathbb{L}) is a largeness notion and for any Fsube_("fin ")N,FF \subseteq_{\text {fin }} \mathbb{N}, F is 1-dense (n,k,h^(-1)(L))\left(n, k, h^{-1}(\mathbb{L})\right) if and only if h(F)h(F) is 1-dense (n,k,L)(n, k, \mathbb{L})